Can you see the exchange server in the backup servers "My Network Places"->"Entire Network"->"Microsoft Windows Network"->workgroup/domain
If not it may be a NetBT name resolution issue ( the "computer browser" service seems a bit dodgy on 2000+ machines ).
I had this problem and resolved it by installing a WINS server on my network, hence replacing the "computer browser" functionality