After a long search around the net I found a simple way to make leopard enable time machine for any backup system. This includes backup up to a NFS or Samba share over a network. Simple open Terminal.app and run the following command:

defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1

That’s it, after that you should be able to choose your mounted volume in time machine for backup. Now I just need to figure out how to force time machine to backup to a subdirectory rather than my linux home directory. I might have to make an explicit Samba share for that.

Edit based on someone’s comment

If the above command isn’t working for you try using sudo:

sudo defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1