Although I prefer my DYI backup system, I also tried Time Machine on my Mac Mini, on Leopard.

Problem: After making some save sessions ok, Time Machine was in 'update' status for hours without saving anything, forcing me to reboot the machine (could not even kill the app cleanly)!

I changed the disk format to GUID as suggest in http://support.apple.com/kb/TS1550?viewlocale=en_US, still had the problem.

I finally found it was due to the fire wire cable. I changed to USB2 connection: no problem anymore!

No clue if it was the electronic on board the external drive (no-name hardware) or compatibility or bug in Leopard, anyway changing the cable solved everything.

May worth to try.