To successfully restore a server you must put a fresh copy of Windows on first. Then install Veritas making sure you can see relevant Tape Drives/Libraries etc. Then restore everything back onto the server. This will overwrite the OS you've just installed and should work fine.
DO NOT do this unless your comfortable with it!
I had to do this recently with WIN2K and it worked fine.