For too long, Time Machine hasn’t been working on my Mac Pro running Mac OS X Server 10.5. Whenever I tried to enable it, a dialog with “Preparing…” would come up, but the backups would never execute. I believe this occurred after I did a restore one time. Anyway, Time Machine backups are now working again after I performed the following in numerical order:

1) Turn Time Machine off (by opening Time Machine’s Preferences…)
2) Trash the com.apple.TimeMachine.plist in /Library/Preferences
3) Restart your Mac
4) Full Spotlight reindex of the Macintosh HD (do this by dragging your hard drive into the privacy window of Spotlight’s preferences or by executing the shell command “sudo mdutil -E /”.
5) Added a bunch of folders to the “Do Not Backup” list in Time Machine
6) Turn Time Machine on