It works! Perform this at your own risk; it’s unsupported.
First set up AFP: http://www.kremalicious.com/2008/06/ubuntu-as-mac-file-server-and-time-machine-volume/
Then make sure you enable using unsupported volumes: http://www.engadget.com/2007/11/10/how-to-enable-time-machine-on-unsupported-volumes/
Now add the new-in-10.6 plist: http://www.insanelymac.com/forum/index.php?showtopic=184462 . (This page actually has a script that sets things up for you; I haven’t tried it but it is a great idea.)