I ran into something similar awhile back. Our server is SBS 2003 Premium, with SQL Server 2000. BackupExec 10 had been running fine with no problems. Then, it started reporting Directory not found or somesuch, but when I would have it test all of ...
My system is exhibiting the same behavior as well, with a similar increase (from roughly 10 hours to around 30!). It has now been relegated to just weekend runs now, obviously.