My initial experiences with time machine were not great, glacially slow initial backup rate, left external HDD in unstable state that could not be repaired, stuck on "preparing" etc. The initial backup rate was minutes per Mb--unacceptable. here are some steps I took, based on watching this and apple support discussion groups--this may not work for all problems being experienced.
turn off time machine
Although TM doesnt require exclusive use of an external drive and will use HDs that have other data, you are placing those data at risk:
before you turn on TM backup anything you have on your intended time machine external disk, partition ( as GUID) first, then erase (format as HFS extended, journaled) and check/repair permissions. (dont let time machine format the disk)
exclude the external disk from spotlight indexing (or turn off spotlight altogether); certainly do not commence initial backup while spotlight is performing initial index after leopard install
turn off any virus checking!!
remove TM plist file from any previous attempts and erase and trash any previous backup files
exclude any large frequently updated database files (Entourage, Parallels) from time machine.
If you have multiple drives that you dont intend including in your routine backup, make sure you exclude them in TM
avoid daisy chained FW drives for the initial backup, time machine disk should be directly connected.
that's about it, Time Machine backed up a ~90G system from a 2.4Ghz SR MBP to a LaCie 500G d2 (FW800) in about 120 minutes and has continued with hourly backups since.
This did the trick for me. Been using TM since Jan and just had it take a crap on me. Tried all sorts of stuff but this did it. Norton is what slows it down biiiig time.