Mac Mail & Exchange 2007

Hello;
We have 8 MACS in a remote office that conected to our Exchange 2003 server. We have now upgraded to Excnange 2007 and MAC mail has stopped working properly.
Oddly enough, setting up a new user on a machine works fine, changing the configuration of an existing account does not work, deleting an existing account and creating new one will not work either, unless you create a user that did not exist on the MAC machine prior to exchange 2007.
Any ideas?
I should add our MAC users also connect to a windows files server that is part of a domain.

Did you name the mailserver the same name? Did you install a certificate for the old mailserver in the users keychain?

The Mailserver had to have a different name (you can't do an inplace upgrade from Exchange 2003 to 2007, so I did a swing install - Micro$oft's way of making life interesting
I'll check with our remote office and ask about the certificate.
Thank you.