Lance,
Please make certain that the cdo.dll and mapi32.dll files on the Exchange server are the most current versions and that they are in appropriate locations available in the system path. Example: x:\program files\exchsrvr\bin\cdo.dll AND x:\winnt\system32\mapi32.dll.
You can also try to unregister and reregister the cdo.dll.
If the Mapistub.dll file is present in the x:\winnt\system32 directory on the Exchange server, rename the file to Mapistub.old and retry the operation.
You can also run the SGmon.exe utility to run the restore in debug mode, it may provide a better error.
Patty