For those of you having problems with Time Machine backups, I finished a support call with Apple today regarding this very problem and I'll run through the steps that the support rep suggested. Like the OP, my Time Machine backups were reaching the "Preparing backup" stage but wouldn't move beyond this point. The Apple support rep told me that they have been getting some calls about this problem and they are looking into it. In the meantime, here is a fix:
1. Go into the System Preferences and click on Security and Privacy to turn off the firewall (if it's turned on).
2. Stop any Time Machine backups that are running either through System Preferences or via the Menu Bar TM icon.
3. Open Finder and scroll down to "Shared" in the left-hand pane, where you should see the name of your Time Machine drive. Double click on the drive.
4. In the window to the right of the pane, you should see "Not Connected". Click on the "Connect As..." button to the right.
5. You should now see the name of your MacBook (and other MacBooks that have been backed up previously, if the drive is shared by several MacBooks). Double click on the name of your MacBook in order to view the Data folder.
6. Double click on the Data folder and find the Backups.backupd folder. Double click on this folder to reveal the Time Machine backups.
7. Delete any âxxxx-xx-xx-xxxxxx.inProgressâ files. If no such files exist (as they did not on my MacBook), delete the folder named Latest.
8. From within the left-hand pane of the Finder window, locate your MacBook hard drive (usually called Macintosh HD) and select it. In the group of folders that appear in the window on the right, open the Library folder and find the Preferences folder.
9. Open the Preferences folder and locate the file named "com.apple.TimeMachine.plist". Delete this file.
10. From within the left-hand pane of the Finder window, dismount the Time Machine drive (see Step 3) by clicking on the upward arrow next to the name of the drive.
11. Restart your MacBook.
12. Open System Preferences and select the Time Machine preferences. Select the Time Machine backup disk and enter the password (if necessary).
13. After Time Machine connected to the backup disk, allow the Time Machine countdown timer to proceed so that the first backup begins.
14. Leave your MacBook running for 24 hours, if necessary. If you have a lot of data on your MacBook, it may take several hours to prepare and verify the backup, before the backup occurs. Be patient. It took my Macbook about 14 hours to run through the preparation and verification stages, before the backup occurred. If you don't have a lot of data on your MacBook, these stages (and the backup) may be completed within an hour or so. Do not close the lid of your MacBook, nor shut it down, until at least the first backup is done. You can use your MacBook during this time, however.
15. Open System Preferences and turn the firewall on (see Step 1).
At this point, your Time Machine backups should proceed without any problems. I hope this helps!