In order to allow Time Machine to use a samba disk for backup, do the following:
1. Mount the samba disk
2. Open terminal and run the following command:
defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1
Now when setting up Time Machine, the samba disk will appear.