Time Machine Error: "The backup volume is read only" on NAS (DNS-323)

I wrote a while back here about how I'd set up my D-Link DNS-323 NAS to allow Time Machine backups from my two macs. All has been going well up to a few days ago when I was greeted with this dialog on my MacBook after an automated backup attempt:

Nothing has changed on my DNS-323 config-wise and my Mac Mini's Time Machine still works fine, using exactly the same network share as my MacBook and the same username and password so I'm more than a little confused by this!

There are literally hundreds of google search results pointing to forum posts discussing this but they all seem to suggest the same thing; after trying the obvious (Use Disk Utility to repair the drive, done... Power off the drive and mac and restart them both, done....) just reformat your drive. I really don't want to do this so I'm going to keep trying. Will report back my findings, but has anyone out there resolved this issue without a reformat?

Maybe this is the reason Apple turned off support for 'unsupported' network volumes afterall? I really hope not.