Last friday, I bought the brand new Leopard. I started installing the new 10.5 on my Mac Pro from scratch.
Everything went fine, except for time machine. This is the result of my investigations, which took quite some time to figure out:

1. Disable time machine
2. Disable spotlight on every internal and external harddisk
3. Enable spotlight disk by disk waiting upon spotlight having finished after each disk
4. Enable time machine (see below)
If you don’t do it this way, it might take up a very long time for spotlight an certainly for time machine to finish its first job.

Update:If you still experience problems with backing up all at once:
1. Format your backup drive as described in other posts (GUID)
2. Exclude everything, except 1 directory with just 50MB or something in it.
3. Start TM
4. Gradually remove some exclusions, so TM can continue the backup… really gradually.
Success