We have exactly the same problem after migrating the Server to W2003 R2 and having done a new installation of BackupEXEC on that Server.
(with take over the Database and Configuration)
There is no file be backed up.
I have done a lot of tests with changes on the backup job.
With different folders, creating new backup jobs, ... --> always the same.
The tests of these jobs are alwalys running OK.
That meens: BackupEXEC checks for new and modified files and gives a summary of the files to backup.
Also: the restore with BackupEXEC works well to the filesystem which we want to backup.
Any ideas?