If you didn’t HAVE to go to a new domain then the easiest would have been to add the new server to the old domain and then migrate the mailboxes between the two servers. If you have to go to a new domain then you will need to setup trusts between the two domains. Then you should be able to migrate the users that way. You will have to use the ADMT to migrate the users over. You would also have to setup a new Exchange Recipient Update Service (RUS). See this article from MS:
as far as the shares, why do you have the shares on the workstations instead of departmental or global shares on the servers? This could create an ACL list and management nightmare. As well as having to make sure that each share on each pc is backed up every night. Look into DFS (Distributed File Systems) or normal departmental shares on the servers to solve this issue. That way there is a single point of backup and single point of management.
<a href=”http://www.msexchange.org/tutorials/Migrating-Small-Business-Server-2003-Exchange-Standard-Part1.html”>Here </a>is a good article on doing what I think you are asking about.