This was such a pain that it seemed worthwhile documenting. My trusty webserver (MacFlowerpot) had been running OS X Tiger since it was first ill-conceived in the gardening department at Lowe's...

I'd been reluctant to upgrade. For starters, Tiger was, IMHO, the single greatest OS improvement in the previous 15 years and it ran great.  Leopard was demonstrably slower in some areas but, as I discovered, it was as fast, if not faster, in general file handling. Time Machine on Snow Leopard was the final decider - it refused to work on Tiger, despite incorporating some Snowy NAS hacks.

Once it was running Leopard, creating the sparsebundle worked first time.
Here's how:
1) Find computer name and ethernet ID (MAC) of machine to back up.
2) Copy/Paste this string in a text editor and change computer name and MAC.
4) Open system profiler and find the UUID.
5) Download this file and paste UUID in between <string> and </string>.
Save to home folder and remove .txt extension if you have one.
6) Copy/Paste this string in a text editor and change computer name and MAC.
cp com.apple.TimeMachine.MachineID.plist <computername_MAC>.sparsebundle/
7) Paste the modified string in terminal - hit return and wait for it to finish.

8) Copy the resulting file over network from your home folder to target volume.

N.B. Time Machine is also supported under FreeNAS:
http://wiki.freenas.org/quick_start_guide_for_freenas_8.0#apple_shares