In Exchange Admin highlight a test user, tools move mailbox. Select the new server.
Assuming it moves with no errors, you should be able to move the lot.
IMPORTANT NOTE - if it looks easy, it has a habit of going pear shaped. Backup everything at least twice before continuing!!! Check the backups worked, then do the above.
You could also do a backup and then restore the mailboxes to a different server.