I had a lengthy discussion with Apple Tech support about this problem. This is an issue that their engineers are investigating. They have mixed user reports; not all users have this problem. As in this forum, virus protection and Western Digital drive seem to be among the most common, but not unique, related software/hardware items. They do not have a defined release date for the next Mavericks update yet. Based on my conversation with Apple, this and related forums, and my own experience (I did get Time Machine working stably), I have the following observations and suggestions:
1. I had all the problems listed in this forum, but Time Machine has been working properly and stably for me under Mavericks now, on one machine.
2. There is a Western Digital Smartware potential issue. I would consider removing Smartware. In my system, Smartware is still running after all the messing around that I did, but Time Machine is working well now. So, Smartware may or may not be the problem. Western Digital has Smartware uninstall programs.
3. There is a new release of Western Digital Drive Manager, and I would install that. I use Western Digital Studio II RAID drives, and I need the WD Drive Manager. I recommend that you install the Drive Manager if it's used for your drives (it might only apply to RAID drives, I don't know.)
4. If you have anti-virus software, either disable the whole thing, or at the least, turn off any background scanning (e.g., idle time scanning) that it does.
5. When upgrading to Mavericks, Spotlight turns on and starts building its index. So, turn off Time Machine until your internal hard drive stops making all the read/write noises. It may take a few hours or days. Let Spot light finish. Go to System Preferences -> Spotlight -> Privacy, and exclude all your external backup drives. You might want to exclude all your external drives for now -- put the non-backup ones back in after all the stuff below is done.
6. The next steps really need your patience -- once Time Machine starts to build or rebuild its databases, let it finish, even if it takes hours or days. Any failure of Time Machine, whether it be a time out, disk access conflict with other programs, or impatience (i.e., force quit and try something different), will cause delays to mount.
7. The "plist" files, noted earlier in this thread, are Macintosh HD -> Library -> com.apple.TimeMachine.plist* (there are two files), contain the Time Machine database file lists. These may be a part of the problem. Put both in your trash (but save them just in case you'll need them again, but you probably won't).
8. Turn on Time Machine, and re-select your drive, don't use the drive already listed -- even if it's the same drive; reselect that drive, and run Time Machine. Time Machine will build a new full backup "plist" file, and it will take time. Let it finish. Mine took two days. The next time Time Machine will turn on, it will begin building/rebuilding the incremental backup file lists. This also will take time, but probably not as long as the initial Time Machine list that you just built.
9. If this is the right solution, Time Machine will now (on the third backup) begin to work properly under Mavericks. After a lot of reading and writing all over user forums, I believe this is what worked for me. My guess is, some parts of it are not necessary, but I don't have a clue which ones. But this combination will work around known multiple programs accessing your disk heavily, and Time Machine database problems.
I think, but am not sure, that the suggestions to reformat Time Machine drives are a draconian solution to deleting the plist files and letting Time Machine rebuild them. If true, the advantage of the latter is that your existing Time Machine backups are preserved.
If this does not work, I'm out of ideas. But I do know that Apple engineers are working this problem, and I'm hopeful that they will include some level of solutions in the next Mavericks release -- whenever that will be. I have two other Macs to update, but am not certain enough of these solutions to attempt updating them until after at least one, probably two, Mavericks update releases occur.
For what it's worth. Good luck! - Andy