So I tried the iPhone Configuration Utility and it didn't work for me either. But here's what did-
Go into Mail, Contacts, Calendars and select the account that has the self-signed certificate.
Go into Account Information
Select the Outgoing Mail Server
Change the Server Port from 587 to 25
When you do this, the Settings app will attempt to verify the account settings. If you have port 25 open on your mail server, it will give you the prompt that you're trying to use a self-signed certificate. Accept the certificate. If you don't have port 25 open, it will give you the error that it can't connect using SSL and will give you the option to try connecting without it. Hit cancel and change the port back to 587, then hit done again and you'll get the same prompt to accept the certificate. It should give you check marks on all the settings and then you should be good to go. If you changed the port to 25 and you want it to be 587 for some reason, just go change it back. You shouldn't have to re-accept the certificate. I've verified that this works on my iPhone 4 and my iPad, on WiFi and 3G and after a power cycle of both devices.
Basically it looks like the MobileMail app doesn't have the proper authority to change trust settings for these self-signed certificates. You have to do it through the Settings app. Just a guess though.
And obviously if you're using port 465 or some other port, just substitute that for 587. Changing the port is just an easy way to get the Settings app to re-verify the server connections, and that's when it'll prompt you to accept the certificate. It's just a faster way than having to delete and re-add the whole mail account.
Incidentally, this also works for CalDAV accounts- just change the port, wait for the error, hit cancel, then change the port back to 8443.