I also experienced this issue and found a fix:
Time Machine is powered by a system utility called backupd. For some reason when I installed the OS, the Created & Modified dates for backupd were set in the future relative to the current date. Before TM runs there are some checks to ensure everything is in order, and if backupd was created in the future relative to the current date, it fails.
I verified this by running the following Terminal command:
which gave the result:
16777221 11087 -rwxr-xr-x 1 root wheel 0 704064 "Nov 5 15:13:22 2013" "Nov 6 04:54:26 2013" "Nov 6 04:54:26 2013" "Sep 30 07:33:37 2013" 4096 1080 0x20 /System/Library/CoreServices/backupd
(You can also just navigate to backupd in the Finder and use Get Info to look at the date there if you prefer.)
The Nov 5 and Nov 6 dates are the Modified and Created dates. The date at the time I was having the error was Nov 4. Hence why it failed.
We can easily fix this by using the touch command in Terminal. I ran:
sudo touch /System/Library/CoreServices/backupd
which resets the relevant dates to the current time when the command is run, thus fixing the problem.
You can test if it’s working by attempting a TM backup. The date check occurs early in the process, so you’ll know if it’s working when it starts to prepare the backup and mount your drive.
You can also fix this by setting the date on your system ahead of the dates backupd was modified/created but this is a temporary fix and using touch to edit the dates on backupd is better. Alternatively you could just wait until the modified/created dates are in the relative past. i.e. in my case waiting until after Nov 6.
Also posted to here http://www.reddit.com/r/applehelp/comments/1pxddr/time_machine_couldnt_complete_the_backup_the/