Always forget this bit:

defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1

Speficially needed if you are using a Linux box, shared by Apple Talk.

From here (Broken link http://www.nextgengeek.com/2011/03/05/howto-use-linux-as-a-networked-timemachine-volume-for-your-mac/) in this instance, although there are loads of howtos.