I'm having basically the same problem. Exchange won't work on the local wifi at the office, but I can use wifi anywhere else (external from office) and exchange will work. Internet and all my apps work, but not exchange email.
If I enter the local IP address of the exchange server in the Host Name setting it works, but then of course since it's a local IP#, it stops working on other wifi spots.
Really bugging me, can't figure it out. It doesn't seem to be resolving the exchange server name properly. Already deleted and recreated the mail account on the iphone. I also have an ipod touch that works fine with exchange on wifi with the same settings.