Are these new iPhones - 3G or with version 2.0 software? If not, they would need to be upgraded - many have tried to make EAS work with older phones, many have failed...including me.
If they are the new phones, do you have the SSL certificate enabled on the Activesync and OMA directories? If so, you would have to use HTTPS and not HTTP to make the connection. Also, if you are using SSL in a single-server environment, you may be experiencing the problem explained in this article:
http://support.microsoft.com/kb/817379