If you just can’t get your Samba server to play nicely with Time Machine (in my case Time Machine would always generate its disk image file without the execute bit set and, it actually being a folder, would then be unable to access it), here’s how you trick them into working together. Create a .sparsebundle and within it a file called com.apple.TimeMachine.MachineID.plist that you fill with the following:

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
  <dict>
    <key>com.apple.backupd.HostUUID</key>
    <string>00000000-0000-0000-0000-000000000000</string>
    <key>com.apple.backupd.ModelID</key>
    <string>MacBookPro5,5</string>
  </dict>
</plist>

Replace 00000000-0000-0000-0000-000000000000 with the hardware UUID you can read in System Profiler.app and MacBookPro5,5 with your model ID, which you can also get from there.