After the OS X Lion upgrade I couldn’t get my Time Machine to work with my Ubuntu based Nas. It turns out Apple bumped the required AFP commands to make it work with TimeMachine. You need AFP 2.2 under Ubuntu to make it work. As I was to lazy to compile it myself I found a easier solution.

sudo add-apt-repository ppa:stefanor/ppa
sudo apt-get update
sudo apt-get install netatalk

Afterwards your TimeMachine should work again.

If you can’t see your TimeMachine Share in the Disk Selection of TimeMachine make sure you executed the following command:

defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1

Bonus:

If you want to limit the size Time Machine will use just append volsizelimit:500000 to your Time Machine share in /etc/netatalk/AppleVolumes.default

500000 is 500 GB

Example of my /etc/netatalk/AppleVolumes.default:

/media/nas/TimeMachine/ TimeMachine options:tm,usedots,upriv,volsizelimit:500000