How to rersolve "Trying to retrieve data from Exchange Server" issues after migration to a new server.

Our organization recently purchased a new server Quad Core Xeon, the old server was a Pentium III eseries and ran Windows 2000 with Exchange 2003. We installed Exchange 2003 with Service Pack 2 on the new server. Migrated the mail store etc. All of the settings are the same on the new server just as the old server, however users some spread across the remote locations are having the same problem of attachments downloads. When double clicking on an attachment the outlook client will hang or freeze. The attachments that do open take a very long time (2-3 minutes) or not at all. All of these users are getting the "Trying to retrieve data for Exchange Server" messages. The outlook clients are a hybrid of Office XP, Office 2003.