I had the same issue at a client a while ago. The iPhones could connect to Exchange using ActiveSync just fine, but they had to always manually do a fetch (send/receive). The Exchange AUTD (always up-to-date) feature wouldn't work.
The problem ended up being that there were host headers configured for the default web site (where the Exchange virtual directories were). I ended up creating a new web site with no host headers, and exported the Exchange virtual directories into this new site and the feature started working fine.
Obviously this might not work for your situation or might not even apply, but I figured I'd throw it out there as a suggestion for something to at least check.