This is happening to countless people right now. It seems that some (not all) of the IMAP servers Apple uses for mail services do not have the correct iCloud password for the user, which causes Mail on the iPhone/iPad/iTouch and the Mac OS X Mail application to frequently throw errors about a password being incorrect (when in fact it is not).
I can verify my password in the iCloud set up screen in iOS, but the Mail application still throws errors.
I am sure Apple is working on this, but please do reply to this thread so they know the scope and grand impact this is having on users.