I am also having the same problem after upgrading to 2010

Today Raid Array of Backup Server Died,

thought it woul be a good idea to switch to new version of BE for reisntall ... i was really bad idea

first setup with server 2008 R2 and a fresh download of Backup Exec from fileconnect.
Everinthings fine execp ... i don't see an information store at our Exchange 2007 CCR Cluster ... nothing ...
first thought maybe the Managment tools are missing ...
so resetup with Server 2008 SP2 ... installed Ex07 Managment tools ...
Installed Backup Exec ...
Same Informations Stores are note displayed ...
Client Problem ? or is the Exchange Agent not recoginezd on the media server ...
serial are registered right ...

now it's 01:30 in the morning .... i need to get my productive backup back on running ..
seems like I'm ending up installing 12,5

just will give it a try to uninstall the agent on the ex cluster an reinstall it

seems like the problme is maybe permission related

getting same error as described her for ex2010
http://seer.entsupport.symantec.com/docs/340684.htm

Wait until you try to uninstall it.  It makes the database incompatible for Backup Exec 12.5.  Symantec has turned Backup Exec into the worst product out there...

Well, not quite...when you upgrade BEWS 12.5 to BEWS 2010, there are some fundamental changes that are made to the software itself. This would include your DB. Once you upgrade it, there is no way to downgrade it, and that would be the same for just about any application (Exchange, SQL etc).
Best bet would have been to make a copy of your DB BEFORE doing the upgrade itself.

Once I put the old 12.5 agent on the exchange box I am now able to see the stores, you may need an additional hotfix for the agent but it should work.