I finally managed to update my series 3 after trying 5-6 times over the last 3 days.
This time I did a restore to the most recent backup, a backup taken after the 6th time of resetting my Watch, basically with nothing on it, no pictures, no music, just default apps etc.
Straight after the restore, in the Watch app on my iPhone I went into General and then Usage. In there there was an item listed for Software Update 2.5 GB. I deleted this which gave me a total of 3.3 GB free. I was then able to update.
I noticed this item of Software Update of 2.5 GB in Usage when trying previously after resetting to new, but it always went away shortly afterwards, so I think you need to delete it straight after restoring/resetting.
Hopefully this method might work for some of you.