The problem seems to be that, for some reason, Time Machine cannot create the relevant sparsebundle file on the network drive to allow the backup to be made. The solution is therefore to create the sparsebundle file yourself rather than letting Time Machine create it.
To get these pieces of information, open up a terminal shell and type "hostname". This will give you the name of your computer.
bart
ether xx:xx:xx:xx:xx:xx (I've replaced the actual values with x's)
Enter the name of the disk image as machinename_macaddress.sparsebundle and ensure that the Image Format field is set to "sparse bundle disk image" and the Partitions field is set to "Hard disk".
When you've entered the information, press the create button. Depending upon the size of the disk you have created this should take a relatively short time.
Time Machine should now be able to perform backups to your network drive.