You may also have been hacked.
My Mobile Me account was hacked, and was sending out 1000 ***** emails a day, and maxing out my account so I could not use it. I only knew about this, because some emails were returned undelivered.
Apple said someone was using my account, and to change the password. I said this could not be so, as I had no outbound emails in my box. They said 'perhaps the hacker is deleting the emails after sending them'. Yeah, right. But I did not want to change my password, as their new password rules are crazy.
Apple's response was to disable my account, so it said 'password invalid', just like yours. So I was forced to change the password.
I think it is clear that someone has broken into Mobile Me, and perhaps iCloud too and iff so, that is a problem.
What you have experienced, though annoying, doesn't necessarily mean someone has hacked your account, though if you were finding that you were blocked because the sending limit had been reached that might indicate that you had been hacked.
What can happen is that when people receive emails which appear to come from their own address but they haven't sent they naturally tend to be concerned: however it's most unlikely that anyone has hacked their account, they've just been targeted by one of two common spammers' techniques: both arise because it's all too easy to forge the 'from' address on messages to be something other than the real one.
There are two methods. One is that the sender has forged the 'from' address to be the same as the 'to' address (so other people will see it coming from themselves, not you), presumably in the hope of confusing spam filters. It's harmless, if extremely annoying. Delete it (never ever answer spam or try to unsubscribe from it), and you don't need to be worried about it.
The other problem is that a spammer is forging your address as the 'from' address on a whole batch of messages. The first thing you hear about this is when you start getting bounce messages because the spam has been sent to non-existent addresses and is being bounced to you. There's no point at all in responding to it. It's infuriating but normally stops after a bit as they move on to another forged address.
There isn't really anything you can do about it: closing the account isn't really worth the hassle unless you are totally swamped, because you will have to tell everyone your new address. Apple can't really do any more than they already are about spam. However changing your password on general principles is a good idea.
It's possible that someone was trying to get into your account - too many attempts would get the password locked out. (With the more common types of usernames you get idiots who get the idea that they own that address and keep trying to get into the account....)
In you situation there is no free iCloud support, but a number of people have been able to get help from MobileMe support - I can't guarantee they will help but it's worth trying. Go to http://www.apple.com/support/mobileme/ww/ and select your country. In the next window click on a category to expand it, then on a subject to get a link to 'live chat'.