I had this problem too. It somehow resolved itself, but I'm guessing it's a bug in the iPhone setup? Or something. Anyway, here's what I did to resolve it:
I disabled the firewall on the mail machine (not sure if this is necessary)
I deleted my old account on the iPhone
I setup a new account on the iPhone
Everything started connecting fine
I re-enabled the firewall on the mail machine
Everything still connects fine.
There's some outside chance that the iPhone is expecting a response on some firewalled port, but I'm not sure which (as I have 25, 80, 110, 143, 443, 993,and 995 open). | 
Bugzilla
Wiki
Source
Linear Mode
