FYI:

Media server:
Backup exec 12.5
Win 2k3 sp2 -fully pathced
Nas:
Iomega 450r
Win Storage Server 2k3 SP2 -stock from vendor

I just got a new Iomega 450r and I run one file server to it. The job ran fine until it got to the verify stage where it said "Queued" and status, 0% complete. It would run and run forever without verifying one single byte. I reset perissions on the nas to even allow "Everyone" full access, in addition to the backup exec account which starts all the services on the media server. I shut off antivirus, rebooted, and defragged the machine but still nothing would make it verify. I had updated the Media server with patches and then rebooted as well. When I shut off verify, the job finishes fine. Job type is 1 Full using archive bit and AOFO and then I run 1 daily incrementals resetting archive bit 6 more times (to finish out 7 days of backups) with AOFO.

I figured out that once i disabled NFS server the job works just fine, but I have not figured out what causes the error yet. Maybe someone else has figured out why that happens, but for now, I'm leaving the service stopped.