The upgrade to Snow Leopard breaks 10.5.x Time Machine backups configured with AFP shares on network volumes, as per this older hint, for example.
After some trial and error, I was able to find out that the secrect lies with a hidden property list file that specifies the hardware UUID for the machine to be backed up. The following are some simple instructions to set up a new backup volume from scratch. They may work for upgrading a Leopard Time Machine disk to Snow Leopard, but I have not been able to verify this.
Setup: If your Time Machine is already configured to back up to a networked AFP share, move on to the next step. Otherwise, follow the setup procedure in the above-linked hint.
Simple method: Use the script and directions that I posted on the InsanelyMac forums.
Manual method:
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
<key>com.apple.backupd.HostUUID</key>
<string>YOURUUIDHERE</string>
</dict>
</plist>Mac OS X Hints
http://hints.macworld.com/article.php?story=20090905212640957