Nokia messaging can be a little tricky to set up, especially if it was working fine earlier and it's now pretending to not be set up anymore. Here's a simple procedure to follow:
1) Try entering your other email address and password, if the account was created earlier and contains more than one address. Just because they say use the "first" account, why should we trust them to keep track of something like that properly? You're lucky if they haven't lost BOTH accounts already.
2) Try entering an old email password, if the messaging account is old. Nokia is actually lying about the whole "enter your correct password" thing, just try some old ones. Do you really think if they have trouble verifying the new password they will tell you that? Of course not, they'll give you the same generic error no matter what.
3) Try adding or removing some periods (.) from your email address if it is gmail. You can sometimes trick it into creating a new account that works properly like this rather than wasting your life trying to troubleshoot something that is broken on their end. If all your email accounts aren't gmail, you may be screwed, however.
4) Try changing your email password with the provider, then try it in nokia messaging again. Apparently if it's too simple, Nokia rejects it but fails to tell you. Of course if it's too complicated, it probably won't work either, because, well, you know why.
5) Try restarting your phone. As if that wasn't the first thing you did. Hell, it probably restarted itself for no reason anyways.
6) Try waiting one or two months and see if Nokia fixes this service. Hint: It's been broken for more than one or two months.
7) Try connecting your phone through a different internet connection. God only knows what it's actually doing, since it doesn't really give us the real error messages. It couldn't hurt to try.
8) Try restoring your phone to it's default settings. I tried restoring a backup, but that caused messaging to break. So, just give up the hours you've spend customizing the phone and revert to stock. It's totally worth it.
9) Try searching for the error message you're getting, unless it says "Problem setting up the mailbox. Please check settings and try again later. (1b03)". That means everything was successful except the part about getting your email set up on your phone. Go sit in the corner until Nokia says you can read your email.
10) When typing in your email address, if you hold down space to get an '@', you get a popup saying that you can't use the invalid character (space) and then it deletes both the space, one letter of your email address (before the @) and then inserts the @.

-edit-

I was getting that last error i listed above. No idea why, since the account was set up and working fine, then today I noticed I'm not getting any email and it appears to be missing from the program and I cannot add it back. Also couldn't log into email.nokia.com with any email/password combination. I actually use a 3rd party password management tool so it's not possible I've forgotten my password or something. I got it working by restoring my phone backup "communication and calendar" to an ealier date. I think the settings on the phone were corrupted, the latest backups are missing the nokia messaging stuff that should be here: \var\lib\gconf\apps\modest\server_accounts\

update:
I contacted nokia support and their official response was to "wait" and then try 'saving' my account again. I verified that I can log into my nokia messaging fine today on their website, so I guess it really was broken yesterday. Or something.

Any news on this? I'm getting the 1b03 error trying to set up my gmail with nokia messaging again. Don't know what to do...

Cheers
K

Guys I'm having major issues with nokia messaging app. on my Nokia n900. what i have been experiencing is that after a while the email client just stops synchronizing, i have reinstalled the email client (nokiamessaging modest) several times and even went as far as to reinstall the firmware (PR 1.3) with no luck, each time I try, it works for a short period and then stops again. Can anyone help with this?

I am also having a problem re-setting up nokia messaging after reflashing, any more tips?

I have just experienced 1b03 error...then I tried to login with all addresses I have asigned with Nokia Messaging account, one by one, and it worked. This email address was not address I used to login before, but it's working now.