Yes, it's a good idea to do that. They said that passwords were compromised; I'm really hoping that was a simplification and they really meant to say that "individually salted, hashed passwords have been stolen" but they didn't add that qualification, so you should probably assume the worst.
> If I have the same username and password on another service, should I be rushing off to change my password right now?
My answer to this question is completely unaffected by the potential data leak at Sony: Yes. Yes you should.
Do you know that all the places you use that password for hash it correctly? You seem to be unsure (as is everyone else) on whether or not Sony stores passwords in plaintext, so why risk it? The only way you'll find out for sure whether or not you are at risk is if one of your accounts is compromised, so rather than waiting to find out I would take preventative action now.
Personally, if I had a PSN account, I would do this immediately. Sony's announcement specifically stated that the hackers got email addresses, PSN usernames, and passwords (among other things). Assuming they properly salted and hashed all the passwords, then it should take a long time to crack them, but I wouldn't take my chances with that. Even big companies have been known to screw up basic things when it comes to security.
If I have the same username and password on another service, should I be rushing off to change my password right now?