are there active connections to the new database?
right click the new, empty database in Enterprise Manager choose the option to Detach Database and verify that the current connections is set to 0..........if there is 1 or more clear them out and retry the restore.
how long does the restore take to run? if it finishes in a couple of minutes (the time it takes to queue up the tape) and immediately finishes it is most likely because backup exec cannot obtain a lock on the database