All of the other devices were working fine.
Here's how I got it to work again:
- First sign out from the affected Mac.
- Then go into Keychain Access. In the list of Keys, seek out a Key called MobileMe Password which has the Cloud icon beside it. It's probably in the Login keychain. Right Click (Ctrl+Click) on this and delete it.
- Now sign in to MobileMe via Preferences and all will be well. Click on Account and then Advanced and Register your Mac.
- When you've done that, select items to Sync and when prompted choose Merge -- this is vital to preserve what's on your Mac.
[crarko adds: This sounds like a damaged Keychain, or something getting scrambled with the encryption. I've typically see this with Wi-Fi keys or email passwords getting messed up in the Keychain, and the solution was the same.]

