Sorry to revive this thread, but I'm having the same problem..
I tried:
- TM fix ( from the topic in #leopard )
- Repairing permissions
- Disabling / enabling TM
- Formatting the Drive, and gave it another name as well
- Installing another SMBIOS ( macdotnub )
- the xattr method mentioned in this thread.

What else can I try?
I'm on 10.5.4,
AppleSMBIOS 1.0.13
IONetworkingFamily 1.6.0

edit: my backup drive is in MBR