Time Machine Error - The backup disk is not available
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.