Since you have both servers up and running, why not just move the mailboxes from one server to the other using Active Directory Users and Computers? When the user logs on to outlook for the first time, the server name will automatically be updated in their outlook profile.
Restore the public folders to the new server from the backup. Rehome the public folders from the old server to the new server. Thats it!