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: (/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.