This was extremely helpful to me. Thanks. Basically it seems the iPhone assumes you want SSL turned on when doing IMAP, and it does not give you a way to turn if off until AFTER you have set up your mail. The advanced settings button does not even show up until AFTER you have the account saved, and every time you try to save it, you get error messages. So your steps below save the day, but I added a couple of more.
1) Enter Mail on iPhone
2) Select Other from the list of mail provider options
3) Enter all the Account specifics, in my case it was IMAP stuf
4) Click Save, and get the invalid certificate message
5) Click "CANCEL", an you get returned to the settings screen
6) Click "SAVE" again, it says, "You may not be able to receive email..."
7) Click OK
8) Now you can go back into the settings, and preso chango, the ADVANCED button now shows up at the bottom of the mail screen.
9) NOW you can go into the advance tab and turn OFF SSL for both sending and receiving mail.
What a pain, but it works.