Suddenly I started getting error when trying to save any new contact using web version of CiviCRM 4.5.3. Persisted for several days now, across 3 different browsers. Looks like this, any advice?:
This says that PHP is trying to connect to an external server and failing. Generally, that would suggest that the DNS settings of the server are no longer correct.
Since you're experiencing this problem on save, the lookup is probably that of geocoding. I would try to disable your geocoding provider to see if it solves the immediate issue. However, the long-term solution is to figure out whether a particular service is gone, your server can't find it, etc.