Mac – Time Machine Backups are incredibly slow, not doing what they should

I have a Late 2008 MacBook Pro that got a new HDD, top case, and RAM within the last week. The previous HDD failed and was replaced by Apple. Using Carbon Copy Cloner and restoring various directories manually to my home folder from Time Machine, I was easily and quickly able to get the computer back to what I believed was its state at the time just before the HDD failed. Now, however, Time Machine is not working properly at all. The incremental backups, which previously were running at what I would consider excellent speed (most were small, in the KB range) took seconds. Now things are much different.

The backups that have run take an average of about 2.5 hours a piece, and run one followed immediately by another. Each of the last four backups shows roughly the same number of files (255,000 – 277,000) being copied by Time Machine. I assure you I am letting the machine sit and no files are being changed by me. After each backup, Time Machine then goes and either deletes expired files (which so far have been backups just over a month old) or performs post backup thinning. It initially performed consecutive full backups, eating up > 100 GB of my backup, and now is doing smaller ones that take roughly the same amount of time. What's more, after each of the last four backups, I have seen an increase in available space on the backup partition, which is less than 1/2 full. There are actually several other problems, but the details are less important than the big picture, which is that Time Machine is clearly not indexing and backing up properly.

Please see the most recent backupd log below (note that these do not show the increase in space that Time Machine is reporting via System Prefs):

May 16 00:46:32 Howard com.apple.backupd[441]: No pre-backup thinning needed: 107.5 MB requested (including padding), 115.28 GB available
May 16 01:11:31 Howard com.apple.backupd[441]: Copied 277591 files (80.0 MB) from volume Metal.
May 16 01:20:49 Howard com.apple.backupd[441]: No pre-backup thinning needed: 100.0 MB requested (including padding), 115.11 GB available
May 16 01:42:56 Howard com.apple.backupd[441]: Copied 258313 files (502 KB) from volume Metal.
May 16 02:10:37 Howard com.apple.backupd[441]: Starting post-backup thinning
May 16 02:12:36 Howard com.apple.backupd[441]: Deleted backup /Volumes/C3PO/Backups.backupdb/Howard Buddin/2012-04-02-114830: 115.16 GB now available
May 16 02:12:36 Howard com.apple.backupd[441]: Post-back up thinning complete: 1 expired backups removed
May 16 02:12:37 Howard com.apple.backupd[441]: Backup completed successfully.
May 16 06:00:33 Howard com.apple.backupd[774]: Starting standard backup
May 16 06:00:33 Howard com.apple.backupd[774]: Backing up to: /Volumes/C3PO/Backups.backupdb
May 16 06:09:53 Howard com.apple.backupd[774]: No pre-backup thinning needed: 100.0 MB requested (including padding), 115.16 GB available
May 16 06:32:39 Howard com.apple.backupd[774]: Copied 277591 files (610 KB) from volume Metal.
May 16 06:41:51 Howard com.apple.backupd[774]: No pre-backup thinning needed: 100.0 MB requested (including padding), 115.06 GB available
May 16 07:04:16 Howard com.apple.backupd[774]: Copied 258312 files (526 KB) from volume Metal.
May 16 07:22:43 Howard com.apple.backupd[774]: Backup deletion was canceled by user
May 16 07:22:43 Howard com.apple.backupd[774]: Starting post-backup thinning
May 16 07:22:44 Howard com.apple.backupd[774]: Backup completed successfully.
May 16 12:59:45 Howard com.apple.backupd[296]: Starting standard backup
May 16 12:59:46 Howard com.apple.backupd[296]: Backing up to: /Volumes/C3PO/Backups.backupdb
May 16 13:02:10 Howard com.apple.backupd[296]: Backup canceled.

I have tried repairing the disk, deleting the com.apple prefs file, and a few other things on Pondini.org to absolutely no avail – the only thing that hasn't worked is deleting the .Spotlight-V100 file, which gives me the message that it is in use and can't be deleted. I have not removed it (yet) with rm -rf /path/ but am tempted to.

So far I have not found a good solution to this problem. Should I just wipe and reformat, losing my backups or does someone have a solution to this??