If you receive the subject error, you will also have the following event:
Event ID: 1081
Source: MSExchangeIS
Description: MSExchangeIS is unable to recover the database because error 0x00000057 occurred after a restore operation.
NOTE: 0x00000057 is the hexidecimal equivalent of 87 ((7*1) + (5*16)).
The Restore In Progress registry key is incorrect. Use Regedt32 to navigate to:
HKEY_LOCAL_MACHINE\System\CurrentControlSet\Service\MSExchangeIS\Restore In Progress
Chances are the paths at EDB_RstMap, a type REG_MULTI_SZ value, are incorrect. Here is correct sample:
\\<Server_Name>\D$\exchsrvr\mdbdata\priv.edb
\\<Server_Name>\D$\exchsrvr\mdbdata\priv.edb
\\<Server_Name>\D$\exchsrvr\mdbdata\pub.edb
\\<Server_Name>\D$\exchsrvr\mdbdata\pub.edb
Either locate/fix the error(s) and start the Information Store or delete the Restore In Progress key and restore the database again.*
* You may want to rethink the backup program you are using. I strongly suggest that you look at
UltraBac.