Wow, this problem is still happening for people!?
Geesh.
I recreated the problem once while setting up my friend's computer for the first time... but then in several subsequent fresh installs of 10.8.x (updating to 10.8.3) on other machines I haven't had the problem.
I had the problem under Lion 10.7.x on 5 computers and managed to fix it before they released a successful fix. But that boiled down to spotlight ....but this Mountain Lion Time Machine problem is a hairier beast.
**
Summary of Fixes (incomplete)
Mountain Lion Time Machine:
-tmdiagnose fix: that fix seemed to work because it doesn't just diagnose, it actually does something. But what it does was debatable so people would downplay that solution (much like they used to downplay repairing permissions with Disk Utility...something that magically fixes many things...) So who knows what tmdiagnose does but it seems harmless and seemed to help me.
-network settings: some people would turn off DHCP and put in a manual IP address...some people needed to be on automatic...Feel like there was more to this.... wireless vs. wired? I know that under Snow Leopard (definitely Leopard), Time Machine was interwoven with the networking driver so that if your networking driver wasn't quite right, Time Machine wouldn't work at all. So I do wonder if toggling these settings doesn't somehow "fix" the networking driver for Time Machine.
-Spotlight fixes: This involved finding the hidden spotlight files on each drive, deleting them....hiding the drives from Spotlight using System Preferences--> Privacy ... then disabling Spotlight altogether via Terminal commands. I had to do variations of these, sometimes more aggressive, sometimes less...The idea is to really clean and, if necessary, suspend Spotlight...to make sure it's not somehow causing an indexing loop with Time Machine.
-Activity Monitor investigation: if you pull this up and set it to show all processes...then sort by highest at top, you might see a process on your computer going bonkers. I've had one called "syslog.d" come up crazy which required magicks beyond the scope of this post. But worth noting what's going bonkers while you're trying to back up....
-Repairing Permissions... you can Repair Permissions from Disk Utility (I don't even bother Verifying first....if there's a Permission that needs repairing, get it done!) ...sometimes you will see errors no matter how many times you run Repair Permissions. Yeah yeah, complain to Apple Long story short, you kinda have to get a sense of which ones aren't real errors. But do it a couple times if you see errors (Repair Permissions while highlighted on the second line of your hard drive in the hard drive list... not Repair Disk)
The next level of this trick is to boot from your recovery USB stick and Repair Permissions while booted from this stick.
-Reformatting the computer.... This tends to work best But one person reformatted and tried to restore from his Time Machine backup at first AND HE STILL HAD THE PROBLEM. The backup restored the Time Machine problem for him! So then he realized if he just reformatted the computer and reinstalled all his Application and User info himself, he solved the Time Machine problem. This is unfortunate for people who don't really want to set up everything again.
Course, one could try restoring your user info from a backup without restoring your applicattions ....He was of the belief that one of his restored Applications was the real culprit but he couldn't figure out which (some people thought that Dropbox needed to be updated but that wasn't universal)
.....
I fell off this Discussion Board at this point so am not sure if anything new came up...
**
How to get SOME kind of backup:
And how to get a decent backup in the first place, if Time Machine isn't working!? Carbon Copy Cloner or SuperDuper are great. Not sure if they cost anything now. This way you can make a perfect clone of your drive (or 2 clones!) before you start mucking about with it...you can restore stuff from the clone using Apple's Migration Assistant if you want to go that route.... if it's too frustrating in the end, you can clone back from the clone to your computer.... But yeah, I suggest 2 clones to hedge against, um, "operator error."
Carbon Copy Cloner and SuperDuper have no problems copying data to/from external hard drives!
**
As for Time Capsules:
I like Time Capsules but i've had 5 different ones have trouble, spanning as many environments and models. But assuming the Time Capsule is working great otherwise, your first backup you should do wired. Choosing Gigabit (1000Mbps ) vs. Wireless (54Mpbs) that first time means you will get a straight backup in spite of how you've got your wireless environment set up. It is sooooo much faster.
Yeah, wireless should work, but I've had problems with Wireless N if the people don't have direct line-of-sight...Heck, I've had some homes where Wireless G couldn't get through the walls! I had to daisy chain Linksys WRT54GL DD-WRT routers to bounce the signal around. You can mess with the radios and channels on the Time Capsule but sometimes even that isn't enough. Most people will have an easy time of it but I've encountered problems often enough that the only way to minimize variables here is to use a Cat 6 or Cat5e ethernet cable between you and the Time Capsule and turn off your computer's wireless to force it to use the ethernet. (You probably have Cat5 cables ...they're OK but you won't get the best speeds... better than nothing)
This doesn't solve the problem AT ALL but will let you see what your system will do under ideal Time Capsule circumstances.
**
Data Corruption:
I personally use a program called Chronosync to schedule daily backups of parts of my computers/drives rather than the whole thing. I like that there is a "verify data" step -- takes twice as long but I do it at night and it goes to that question of "losing bits" .... I've had computers for almost 20 years and that means moving data through a lot of machines over that time. I started getting into the habit of using Chronosync because it should detect errors if it hits corrupted data, and then I can see if I can find another copy of the file before I entrust my system. Now, how many times have I encountered corrupted data from a system copy? Not often... handful of times so far maybe? (and Carbon Copy Cloner caught one once or twice!) And not often enough to really matter, in the scheme of things. But I like the purity of a perfect (well, double-checked) copy. But for most people, that's overkill. I don't worry about wireless/wired loss because anything significant I transmit is verified by Chronosync...