It was getting to the point where it looked like it was working, but once it actually began backing up, it would get to about 100kb, and then fail with this message in the system log on the Mac:
Oct 29 16:37:48 my-macbook mds[38]: (/Volumes/Backup of MyMac/.Spotlight-V100/Store-V1/Stores/XXX-XXX-XXX-XXX-XXX) (Error) IndexSDB in si_writeBackDBO:Error 2 storing dbo(9770a3,430,182,4b076d10a69e9,0,1d1686,0)
I was able to follow the instructions copied below from a comment on this page:
Obviously I didn't follow them exactly, since I have an Ubuntu server and not a Mac OSX server, but it now turns out that my Mac now creates the sparsebundle file for me! I basically deleted the whole folder (sparsebundle that I had created for the previous version of Mac OS) that I was using for the netatalk share, created an empty one with 777 perms, added the .com.apple.timemachine.supported file, and my Mac did the rest!
Note: The backup did fail once or twice after following these instructions, the third time it started working all by itself, all I did was retry.
10.6: Set up Time Machine on networked AFP volume
1. Create an AFP share on an OS X machine (set permissions, user accounts & passwords as you like)
2. Run `touch .com.apple.timemachine.supported` from Terminal.app on that share
3. Mount the AFP share by clicking around in Finder
4. Point Time Machine to the disk
It then goes off to create a .sparsebundle, mounts that and does a backup.
I may have run the magic `defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1` way back when, so you may have to run that too.
Both machines run 10.6.6, but I (maybe miss-)remember doing it like that on Leopard too.
(Before anyone says this doesn't work anymore, I'm doing an initial backup using that method right now)