The upgrade to Snow Leopard breaks 10.5.x time machine backups configured with AFP shares on non-mac based network volumes as per these instructions, 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 TM disk to SL, but I have not been able to verify this. Attached are a shell script that will do all the work for you and a property list file in case you want to try it yourself.

1. SETUP

If your time machine is already configured to backup to a networked AFP share, move on to the next step. Otherwise, follow the setup procedure in the link above.

2. SIMPLE PROCEDURE

Run the attached shell script with command line arguments specifying the maximum size for your backup image and the shared directory you want to backup to (the second argument is optional).

Example:
This will create a time machine ready disk image named with your computer's name with a maximum size of 600GB and copy it to /Volumes/backup. The image "file" (it's a directory, really) will contain the property list file that SL's TM needs.

If you don't specify the backup volume, you will need to do the coying yourself:
You may or may not have to execute the script and the copy command as root. I have not tried it out both ways and only done it as root.

3. "MANUAL" PROCEDURE

a. Create a disk image named with the name of your machine's computer name (not sure that this is crucial; you can find it in System Preferences -> Sharing). This example is for a 500GB (max size) image for a machine named snowy:
b. Edit the attached com.apple.TimeMachine.MachineID.plist file and copy your machine's hardware UUID in the correct place. You can find your hardware UUID in the System Profiler

c. Copy the modified com.apple.TimeMachine.MachineID.plist file into your disk image directory:
d. Copy your disk image file to your mounted backup volume. This example assumes an AFP share with the name backups:

Please let me know if you run into any issues. The attached script works for me but it may not work for you. I make no guarantees whatsoever!!

NOTE: remove the '.txt' extension from the attached files.

UPDATE 9/6/9: Fixed shell script to handle computer names with spaces.
UPDATE 9/24/9: We made it onto macosxhints.com