What is the version and edition of Operating system, you are backing up? Is this DFSR or DFS? Have you tried selecting differential or incremental in the general tab of backup job properties? What version of Backup Exec is this? Please make sure all the patches are applied to Backup Exec and the remote machine being backed up.
Thanks