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.