Here's what I did after reading several articles about this:
defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1
Connect to your network drive and save your password
Open Time Machine Preferences:
Select your Volume
Click Backup Now or wait for it to start.
Look on your volume and you will see a file called:
machinename_3493951911.sparsebundle or something similar
copy the first part not including sparsebundle
Wait for time machine to fail :-(
Open Disk Utility and click New Image
Paste in the name you copied and choose Desktop as the location. Change the type to sparsebundle. Give it a reasonable size and click create.
Unmount it and copy this file to your network drive. it should be about 80MB. Now go back to time machine preferences and reselect your network share. Click backup now and you are good to go!