LegalGeek's steps have been the best so far.
Although I do feel like some people have had success with backup drive reformats and fiddling with Spotlight.
Apple obviously changed something with 10.7.5 and 10.8.2 that created/revealed this disaster, however you want to slice it They fixed it with the 10.7.5 supplemental update (note no excuses from them there that it was a third-party problem) but they haven't been able (or cared) to fix it with 10.8.2.
I did a silly thing and, knowing everything from this thread, updated my GF's brand new MBP from 10.8 to 10.8.2, installed a bunch of apps, and ran Time Machine to back up her 200GB to a local USB-connected drive before I finally realized what I had done. Noooooooooo. The back up said it was going to take 5 hours, which sounded long, but when it started choking after a pause/resume (think it said 1000 days at one point) I would have been grateful for the 5 hours!
I didn't have time to extensively try a technique of swapping out the IONetworkingFamily.kext (which TM historically relies on) from an old Mt. Lion install but I did try it and it seemed to get things back down to 5 hours. But that's not realistic for others, wasn't scientific enough to explain now, and I restored the original kext driver.
But I DID do a few things that may have helped and that would be doable for others, but you must be very careful:
1) First back up your computer some other way... Carbon Copy Cloner has a full 30-day trial so you can use that but just pay attention to your settings so you don't inadvertently wipe out your target/destination drive (unless you want to)... I like to use CCC to back up to a new sparsebundle disk image on a backup drive.
If you have room on your existing backup drive for a full clone and a full Time Machine, you can use the same backup drive; otherwise choose another location for your clone.
2) Doublecheck your backup
3) Delete your current partial/busted Time Machine from your backup drive... Might be called backups.backupd if on a local drive or "drivename.sparsebundle" if on a network drive.... empty the trash
4) I went into my System Preferences and turned TM off for the moment... if you know how, you can tell it not to back up to any drive for now...although I didn't easily see that in Mt. Lion.
5) I went into System Preferences for Spotlight and added the TM drive to the Privacy/exclusions list... now if your drive is on the network, I bet you could mount the drive on the network and add the mounted drive to the Privacy list... Honestly, for the sake of thoroughness, add the TM drive to the Privacy lists of any computer involved in your backup process (source and destination).
6) Here's the "dangerous" step because it involves a powerful Terminal command to nuke Spotlight on the backup drive. Long as you type it correctly, you'll be fine So fire up Terminal on the backup drive's computer (I use Spotlight to launch it but it is just in your Applications --> Utilities folder) ...
WAIT, did you see what I said: Launch Terminal on whichever computer that has the backup drive attached to it...forget mucking with this over the network (although doable).
OKay, firstly
type this innocuous command to get to the right drive:
cd /Volumes/<NameOfYourBackupDrive>
(I just type cd /Volumes/ and then the first few letters of the backup drive, then I press the "tab" key and it will fill in the whole drive name for you...then press return.. if it doesn't, you've mispelled it or you have multiple drives beginning with the same letters...type more letters...check your caps lock... this stuff is case sensitive)
press return to have Terminal go to the backup volume....
Okay, so the resulting prompt should give you a sense of where you are...
you can type the following to see what's in the directory...totally safe:
ls -al
(that is "el ess dash a el")
press return
You should see ".Spotlight-V100" in the list
CRITICAL STEP, CAREFUL NOW:
So to delete that you type, very carefully:
sudo rm -R .Spotlight-V100/
you see that dot in front of Spotlight?! yeah, there's a dot...otherwise it won't find that file at all (it's hidden)
Press return...It will ask for your computer password.... for me it took a long time to delete! Which made me think, wow, there must be a lot of crap in that Spotlight directory already!
7) Alright! Almost done... Now just get back on the original computer you are trying to back up and you're going to restart into Recovery mode so you can run a basic Repair Permissions.... To get into Recovery mode you restart the computer and then hold down the "option" button after you hear the *bong* ... I think I read that you can get there by holding "command and R" at the same time after the *bong* but I haven't tried that.
Anyway, get into Recovery... it will take a few minutes to boot up... then use the menu/Utilities whatever to fire up Disk Utility... highlight your main computer drive (or the indented line right beneath it) and hit "Repair Permissions" down below... this is totally innocent/great ... Don't Verify...waste of time... and Repair Disk can be a bit more aggressive so it's not necessary... just Repair Disk Permissions.
Phew.... after that...quit out and restart the computer.
8) Alright... set up a new Time Machine to the drive we cleaned up earlier and see what happens! For me 200GB still said it was going to take 5 hours but that was going to be better than days.... AND it was 650,000 items so that can matter more than the total size... lots of little bits and bytes