I have my Hotmail account working fine on my iPhone 4S. Did you set it up new or did you resync it over from a backup (if you had a previous iPhone)? I had one setup previously, but discovered that they made some improvements to Hotmail support somewhere along the line (I think iOS 4) and my initial setup must have been prior to that. Long story short, I couldn't delete email on my iPhone and have it delete it on the Hotmail server. But now they do support that, but I had to delete my account and add it as new to get that to work right.
For your situation, it sounds like you entered your password wrong. Also, make sure that the error message you're seeing is definitely referencing your Hotmail account (in case you have multiple email accounts on your phone, it's possible that you may be looking at your Hotmail account but the phone is trying to fetch email from a different account in the background and it's popping up with an error in regards to that other account).