Can I use Time Machine to backup to a Ubuntu File Server?
This answer explains things for a Windows-based server, but it should work fine for Ubuntu.


In Terminal, type the following command:

defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1
Now, as long as you have a connection to your computer’s shared drive, you should be able to see it in Time Machine.
To connect to that shared drive: Finder > Go > Connect to Server.
Type in the IP address or host name of the server. You may be prompted to log in.
Configure Time Machine to use the drive, and try creating a backup.
Time Machine will try to create a “sparse bundle” on the drive, and will fail. 
Open Console and check system.log. You will see the name of the file Time Machine was trying to create. The name of the file will be something like .MacBook Pro_00254bd7abe8.sparsebundle
You will need to create a sparse bundle with this name and put it on the hard drive manually before the backups will work. To do this, open Disk Utility.
Click New Image > Set image format as “sparse bundle disk image” > Set partition map to “no partition map” > Set the size as the maximum size you are willing to allot to Time Machine. Don’t modify anything else.
Though the file on the hard drive will need to begin with a period, you will not be able to do this right away through Disk Utility, so just call it whatever you want right now.
You can rename the file so that it has a period before its name from Terminal on OS X or Ubuntu. Your final name should be like .MacBook Pro_00254bd7abe8.sparsebundle.
If everything is done right, you should now be able to use Time Machine with an Ubuntu Server.


Note: This answer was copied from MacRumors and has been formatted for AskDifferent. I’ve used this method myself, albeit on a Windows shared drive.