A few days I ago I decided to change all my passwords. It was a precautionary measure, prompted by some spam emails sent out to users at eBay, ostensibly from my eBay account—an account which eBay temporarily suspended later that day.
I haven't bought anything on eBay in over a year, but I do get a lot of spam that mentions the company, so when I saw some emails to me, supposedly from my own account, I figured everything was spoofed and just spam, and turfed them without thinking further. Then I received an official-looking message apparently from eBay itself, titled "TKO NOTICE: eBay Registration Suspension - Possible Unauthorized Account Use." It looked a bit more legit, but I know better than to click links within emails like that, so I signed in at eBay itself.
Sure enough, my account had been suspended, apparently because of spam complaints from other eBay users. After a live support chat, I was reinstated and I changed my password. I'm still not sure whether the outgoing spam mails were spoofed, or if someone hacked into my eBay account. So just to be safe, I changed passwords everywhere else (email, Amazon, .Mac, Flickr, blogs, and so on).
By the way, if you want a really good password, I have a couple of recommendations: the built-in Password Assistant in Mac OS X (which has options to create strong passwords that are still memorable, as well as evaluate whether a password you choose yourself is strong enough), and Steve Gibson's Perfect Passwords page (which creates really insane passwords that no one could ever guess).