When you created the backup job in Arcserve you will have been asked for certain credentials that have access to the files that you were backing up. Normal practise is to use the NT & 2000 user 'backup' after a few modifications to file properties or the domain admin account.
These same credentials need to be entered, as databasebaba said, into the restore security locaiton before you'll be able to access the files to restore them.