You get the warning, but you are then able to read mail right?
I had a similar problem and received the same warning, but I wasn't able to retrieve or send any mail. Check your mail settings and see if they are correct. If it's a common mail account (yahoo, gmail, etc) the iphone will be able to retrieve the proper settings.
If it isn't a common mail account, like a school mail account, then call the IT help desk to get the correct settings.