Heartbleed OpenSSL bug is currently main computer topic of main-stream media. And they all offer same idiotic advice - change the password. I am not saying that "change the password" mantra is useless. No, it is bloody dangerous.
Let's see what bug does first: it simply allows attacker to read (semi)random 64K block of memory it should not see. And it allows it to repeat that attack until it has all the data it wants. If leaked blocks contain a cookie, somebody can impersonate you. If they contain user name and password, attacker just got a jackpot. If they contain private SSL key, attacker is in heaven.
Based on that fact, password change seems reasonable. But think again. Practically only way OpenSSL might have your password in its memory is if you sent it to him in the first place. When was the last time you actually sent password for e.g. GMail? Answer is a long time ago. Only piece of data server can have for you is your cookie that keeps you logged in. And you can reset that one with a simple logout. But that is not the dangerous part.
If you change password on server that is still compromised, you are putting it in OpenSSL's memory at that exact moment. In essence, you are giving away your newly created password directly to an attacker. And, since password is freshly changed, you probably wont change it for a while. It is WORSE than doing nothing.
For safety first approach log out of any important service you are using. That way you are preventing somebody using your login cookie. Then go and CHECK whether site is compromised. Once you know host is not compromised any more, log in again. And ONLY THEN think about changing the password.
If host is still compromised, do not log onto it. I don't care what is the service it offers. Either it is important (e.g. bank website) or it is not worth the risk.
PS: To summarize: I am not against the password change - it is probably a wise move since this bug has been out for last two years. I am just against doing it irresponsibly, without checking whether site has been fixed first.
PPS: Since you are changing passwords anyhow, be intelligent and use different password for each site.
PPPS: Seems as a good time to turn on two-factor authentication (if website has it).