Time Machine backups failing (error 22) on Time Capsule

Hi

I've been happily using my Time Capsule as a Time Machine backup for the last year or so. Two MacBooks have worked just fine on there, along with a network drive to store some of the wife's files which won't all fit on her Air.

Last night the firmware was updated on the TC and now whenever I try to do a backup on either my MacBook Pro or the MacBook Air I get the following error:

The backup disk image “/Volumes/Data-2/Adrian’s MacBook Pro.sparsebundle” could not be created (error 22).

The backups have always gone into a folder "Data" on the TM previously, and whenever a TM backup began I got a dark green TM disk icon on the desktop. Now this doesn't happen and the above error shows after the TM tries to prepare the disk.

I've tried deleting the .com.apple.timemachine.plist file from the Library Preferences to recreate that, no good. I've tried rebooting both TC and MBP. I've tried moving my old backup to a different folder to start afresh. Nothing has helped.

I also cannot access the old backups - I get this error:

An unexpected error occurred (error code -6584).

I have 1TB space remaining on my 2TB TC, so that shouldn't be an issue. I've tried rolling back the firmware using the Airport Utility as well, but this hasn't helped either.

I'm running OS X Lion 10.7.3 on moth MBP and MBA.

And with that I'm stumped as to why something that was so reliable should now suddenly stop working. The last backup was showing as yesterday at 21:22, which would have been just before I did the update. The only other thing I may have done last night was to map a network drive on the MBA so the wife can connect to her folder on the TC more easily.

Any ideas/solutions gratefully received! Thanks in advance!