I am experiencing exactly the same problem, but I've found that in my case it is because the files are held up by another process, in my case a users Blackberry device is busy synching with Outlook.
It's fine if BE skips the files, since it will just be backed up the next day, but BE is reporting a backup failure. Is there any way to make BE report completed with exceptions (as that is essentially what it is) and not a failure?