I like Bruce Schneier's take on it: "Cryptography is all about safety margins". The larger the key size, the larger the safety margin (and the larger the performance hit). A 512-bit key is probably OK, but probably not for very long. As Shane Madden mentioned, there's ample evidence that they can be broken by a concerted attack in under a few months. If that is enough of a safety margin for you, then you don't immediately need to replace them. 1024-bit keys are probably next to go.
So if you already have Digital Certificates you have purchased that use these key sizes and you are NOT protecting vital company/nuclear secrets you are probably OK for the short term, but you will want to purchase SSL certificates with a larger key size in the future. Is there a big enough safety margin for you? Is it worth the performance hit? Who would be attacking your cryptosystem? A little threat analysis is good for A) figuring out whether you need to do something RIGHT AWAY and B) covering your ass in case something bad happens.
How large a key should be used in the RSA cryptosystem?
As for the slowdown caused by increasing the key size (see Question 3.1.2), doubling the modulus length will, on average, increase the time required for public key operations (encryption and signature verification) by a factor of four, and increase the time taken by private key operations (decryption and signing) by a factor of eight.
As for what that performance penalty will look like in the real world it's really dependent on your application and implementation. It might increase the time by a factor four which only works out to an extra 4/10ths of a second, or it might be four seconds. Testing is important here.
It looks like at this point NIST (SP800-131A) only considers RSA and DSA 2048 key-sizes to be acceptable after 2011-2014 and they must have at least 112 bits of security strength. See the section in SP800-131A on Digital Certificates for more information.
In my opinion it all boils down to this: your safety margin is "small" with 512-bit keys, "not bad" with 1024-bit keys, and "pretty good" with 2048-bit keys. Do a bit of threat analysis and decide how fat your organization's safety margin needs to be, what kind of data you are protecting and what you stand to lose if the cryptosystem protecting it is broken. Make sure to consider existing policy, and any legal requirements you need to comply with.