I just did this:
1) Turn Time Machine off
2) Trash the com.apple.TimeMachine.plist in /Library/Preferences
3) Restart
4) Full Spotlight reindex of the Macintosh HD
5) Added a bunch of folders to the "Do Not Backup" list in Time Machine
6) Turn Time Machine on
Currently Time Machine is doing hourly backups in a matter of minutes again, instead of staying stuck on "Preparing..." for over 40 minutes. I just hope it stays that way because I really don't feel like going through this every month...