Time Machine Error - The backup disk is not available Problem

My automatic backups for my Macs have recently started failing with the following message (same error if I attempt to "Backup Now"):

Time Machine couldn't complete the backup to "DeviceName".
The backup disk is not available.


Every other attempt or so I also get a warning that it was a while ago that a backup succeeded. If I open Time Machine Preferences there is a red icon with an exclamation mark next to the backup disk which if clicked produces the following message:

Time Machine Error
The backup disk is not available.
Latest successful backup: &lt;date&gt;


I just tried to re-select the backup disk from Time Machine Preferences > Select Disk, which worked without problem, but now Time Machine seems to have forgotten all my previous backups (I can still find the backups on disk using Finder, but Time Machine claims that I have no previous backups).

Questions


Now that I have reselected the backup disk, how do I get Time
Machine to find the existing backups? 
Is there another way to get Time Machine to find the backup disk?


Setup: One Macbook Air, one Macbook Pro, one Netgear ReadyNAS Duo claiming to be a TimeCapsule. Both Macs use Mountain Lion.
I've now gotten Time Machine to see the older backups. Not sure if the first step is necessary as I noted that Time Machine Preferences took a while to update the "Latest backup" date, so it might have been enough to just perform a backup.

Step 1 - Verify the backups


Following a guide on a similar topic I deleted the
com.apple.TimeMachine.MachineID.plist file (on my ReadyNAS this was
located under /c/.timemachine/MachineName.sparsebundle/)
Have Time Machine verify your backups by having the alt-key pressed while clicking the Time Machine icon and choosing Verify Backups


At this stage Time Machine Preferences still states that I have no backups, but by choosing Enter Time Machine I can see the earlier backups.

Step 2 - Take a new backup

After this was done, Time Machine Preferences update both the Latest Backup date and Oldest Backup date to correct values.