When you say you restored the info store, did you restore the exchange directory as well?
Sorry if that's an obvious thing to suggest, but I once forgot to do it, and it took me hours to figure out! I use Arcserve, which backs up the directories in a different session.