MacOS – Time Machine stuck on “Preparing Backup”

I have a MacBook Pro from 2009. It came with OS X 10.6 (Snow Leopard) but I upgraded to 10.8 (Mountain Lion).

A few days ago, I tried to backup my files on an external hard drive, like I have successfully done many times before and after the OS upgrade.

The status on the Time Machine menu at the top of my screen said "Preparing Backup", instead of counting up like it usually does. It stayed that way for a few minutes, then I got tired of waiting and stopped the backup.

Last night, I tried it again and let it sit overnight for almost 12 hours. It is still stuck on "Preparing Backup". What can I do to make the backup work like it did before?

I tried Googling for this problem and the solutions I saw said to either wait longer (without any clear idea of how long) or to exclude the Backups.backupdb folder from my virus scanner (which doesn't apply to me since I don't have a virus scanner).

Edit on 2013-5-23: Here are all the things I tried that didn't work:

• I tried waiting for the indexing to finish but that didn't seem to help. I let my laptop sit for about 36 hours and the status still said "Preparing Backup".
• I found a folder on my backup drive named /Volumes/Time Machine Backups/Backups.backupdb/Elias Zamaria’s MacBook Pro (2)/2013-04-30-182726.inProgress. I deleted it and that didn't seem to help.
• I tried verifying my main hard drive using the Disk Utility and everything seemed fine. I tried verifying the disk permissions and got some errors involving iTunes (I think), and I fixed them by clicking the "Repair Disk Permissions" button. I also tried verifying my external hard drive and it seemed fine. I tried the backup again and it froze like before.
• I tried looking at the website that @lgsancho linked to. I found some things that may look useful but I didn't try them yet.

• I tried running tmutil status, without the backup running and got this result:

  Backup session status:
  {
      ClientID = "com.apple.backupd";
      Running = 0;
  }
  

  I started the backup, waited for the status to change to "Preparing Backup", and ran the same command, and got this result:

  Backup session status:
  {
      BackupPhase = ThinningPreBackup;
      ClientID = "com.apple.backupd";
      DateOfStateChange = "2013-05-21 19:09:06 +0000";
      DestinationID = "8BC5795A-0AAC-4976-B960-ECCE8F48842C";
      DestinationMountPoint = "/Volumes/Time Machine Backups";
      Percent = "-1";
      Running = 1;
      Stopping = 0;
  }
  

  The backup has been going on for about 45 minutes. I tried the command and got this result:

  Backup session status:
  {
      BackupPhase = ThinningPreBackup;
      ClientID = "com.apple.backupd";
      DateOfStateChange = "2013-05-21 19:09:06 +0000";
      DestinationID = "8BC5795A-0AAC-4976-B960-ECCE8F48842C";
      DestinationMountPoint = "/Volumes/Time Machine Backups";
      NumberOfChangedItems = 483816;
      Percent = 0;
      Running = 1;
      Stopping = 0;
  }
  

  It looks exactly the same, except the Percent has increased from "-1" to 0.
  The backup has been going on for almost 3 hours. The status still says "Preparing Backup" and tmutil status gives me exactly the same result as the last time.

Here are the things that have been suggested, which I am reluctant to try:

• Emptying my trash. I don't want to do this because it defeats the purpose of the trash and takes away my ability to recover files that I may have accidentally deleted.
• Deleting old backups. I may try this if nothing else I can think of is helpful.

Edit on 2013-6-1: I am unaccepting my answer because it is happening again. I will get sick of rebooting every time it happens. I just want it to stop. I am thinking of considering deleting my old backups. This is what I see in the Console from backupd:

5/31/13 11:09:09.595 PM com.apple.backupd-helper[16259]: Not starting scheduled Time Machine backup - time machine destination not resolvable.
6/1/13 12:09:37.920 AM com.apple.backupd-helper[16438]: Not starting scheduled Time Machine backup - time machine destination not resolvable.
6/1/13 12:23:20.619 AM com.apple.backupd[16473]: Starting automatic backup
6/1/13 12:23:21.794 AM com.apple.backupd[16473]: Backing up to: /Volumes/Time Machine Backups/Backups.backupdb
6/1/13 12:23:26.430 AM com.apple.backupd[16473]: Using file event preflight for Macintosh HD
6/1/13 12:23:55.148 AM com.apple.backupd[16473]: Will copy (829.8 MB) from Macintosh HD
6/1/13 12:23:55.602 AM com.apple.backupd[16473]: Found 14880 files (949.2 MB) needing backup
6/1/13 12:23:55.632 AM com.apple.backupd[16473]: 2.44 GB required (including padding), 391.84 GB available
6/1/13 9:06:02.191 AM com.apple.backupd[16473]: Cancellation timed out - exiting
6/1/13 9:10:04.406 AM com.apple.backupd[18634]: Starting automatic backup
6/1/13 9:10:05.055 AM com.apple.backupd[18634]: Backing up to: /Volumes/Time Machine Backups/Backups.backupdb
6/1/13 9:10:11.788 AM com.apple.backupd[18634]: Using file event preflight for Macintosh HD