I too have been impacted with the sync Exchange over WiFi bug.
I went from an iPhone 3G running OS 3 with no issues syncing mail, etc... to an iPhone 4 with iOS 4. I set the phone up from home on my personal WiFi and added my Exchange email account without problem. Everything seemed normal.
I arrived to work yesterday and noticed that none of my e-mail was coming through to my phone and the phone would sit "Connecting..." forever. I was logged in to my corporate WiFi. Upon disabling WiFi, and the phone on 3G - all my e-mail would sync normally. Connecting to WiFi again replicates the problem. I checked with the other iPhone 4 user in the office and he was having the exact same issue.
Long story short - I upgraded the firmware on the router and changed the encryption method, reset network settings, installed the Apple profile fix, renewed the DHCP lease on my phone, and could not get the Mail application to sync over the internal WiFi at the office - nothing worked.
Additional testing shows that when changing my mail profile to use the internal IP address of the Exchange box, the phone syncs. Using the DNS hostname, it does not. Also, I verified in Safari that I could not access the OWA site at
https://mail.company.com. The request would simply time out and get a page could not be displayed error. Accessing
https://XXX.XXX.XXX.XXX/exchange, the OWA page pops up normally. I was able to ping the Exchange box from the WiFi router.
It seems like name resolution, but I am baffled at why it works on the 3G and 3GS running the 3.0 OS.
Hoping for a fix!