Is this a USB tape drive?
Are you running SP1?
If both answers are yes, there was a problem restoring from some USB tape drives that was fixed in SP2. There was a hotfix for SP1, but it wouldn't be available any longer. However I think that gave a funky error message, so may not be your problem.
MS KB article 817765 describes that problem.
There was also another one whereby you cannot restore from a backup on USB tape if verify was turned on when backed up. MS KB article 328742. I'm not sure if that was fixed in SP2 or not (I stopped using verify).
Jock