I'm posting this to assist anyone else having a simular issue.
Issue: Attempts to restore Exchange server to Recovery Stroage Group Fails after performing all the steps from support, and you receive a messaged access denied or security error.
Possible solution: After two week of trying to restore the same tape from backup to an external USB drive we configured the Recovery storage Group database to place the data on an internal hard drive which worked fine.
It appears that even though you can restore DATA to an external USB drive, the recovery storage Group will not restore to an external USB drive, so if your attempting to restore to a USB drive and it's failing try restoring to a local hard drive even if there is not enought room, you can cancle the restore once you see a byte count.
Ken Corbet