I have the same problem but with ALL my accounts. I am outside US and sent my phone back for repairs, they ended up giving me a new one. I tried to set up my Nokia
Messaging account AGAIN and none of the emails work.
I added one by one and they work just fine...