is it your own exchange server, or a corporate?
I know on our system, we have to use an external webserver for any device that isn't our corporate laptop. If you are trying to use the same one as your PC, it might not work as the MAC won't be accepted by the actual server.
Also, if you have a blackberry, you CAN'T use the exchange settings from that either as there is an intermediary server for BBS.
Check with your IT folks....my guess is that there is something like
ext.yourcompany.com for the server.