Hello everyone. I'm here reading this because of similar Time Machine problems. In my case I'm using Time Machine with a new USB 1TB hard drive connected directly to my iMac. I started using this when I was running Lion probably in February. It had been working fine, even after I updated to Mountain Lion the day it was released.
The initial backup took a while, and then the hourly backups were fairly quick.
Then earlier this week I starting having an issue with my Mac where applications wouldn't launch, and that turned out to be a permissions issue. I don't know what brought it on, but I booted into the recovery partition, checked out the hard drive with Disk Utility, and then repaired the permissions. That fixed that issue.
Upon rebooting, the next hourly Time Machine backup never would get anywhere. In fact two days had gone by without a backup. They wouldn't fail, but they wouldn't finish either. It stayed at about 50MB out of 500 or so MBs for two days. So I found this thread and a few others, and tried the various fixes people proposed; I reset my PRAM. I deleted the Spotlight indexes and let it rebuild them. I ran that command in the terminal. Nothing worked.
I downloaded the Time Machine Buddy widget, and it showed it was "Forcing deep traversal on source".
So I decided that since there wasn't anything in my backup from the beginning of August that I needed, I formatted the backup drive and started over. It said it was going to take 11 days! It didn't take that long the first time I backed up my drive! So I started over again, and now it said 30 days! I stopped it again, reformatted the drive again, ran Disk Warrior on it to optimize the directory, and started over. Now it said it was going to take 12 hours. Great! Left it over night, and... now it says 3 days. It had gone from 4.92 GB to 17GB. I have 553GB of data on my 1TB hard drive.
Finally I decided that was enough. I wasn't going to go any longer without a recent backup. I liked using Time Machine, but honestly I rarely went to retrieve a file from a particular day. The other issue is when it was backing up the Mac became very sluggish, sometimes to the point that I had to stop the backup to get anything done. It wasn't like that in Lion. So I reformatted the drive again, and now I'm using Carbon Copy Cloner. In one hour it has copied 25GB. It took Time machine 8 hours to copy 12GB. I have CCC set up to do hourly backups, and to temporarily archive changed or deleted files, so it should work about the same.
So clearly something broke with Time Machine. This supplemental update to Lion released today says it fixes this issue on Lion, but not the one for Mountain Lion.