After recompiling netatalk the other day in order to get it to work with Leopard, the next step was getting Time Machine to make backups over the network (and a wireless one by the way). 
Problem is: despite the netatalk-powered network shares worked great for “regular” files, when Time Machine started preparing the backup it always gave me an error.
Googling about it I’ve found several stories with different soluctions, some of which worked for some people, some others didn’t. The one that did it for me is this one:
Basically it consists in creating a “sparse bundle” disk image on the local hard drive using MacOS X’s Disk Utility, giving it a specific name, moving it to the network share and then configure Time Machine to use that share.
Worked for me. 