Backup Disk Not Available - Time Capsule

Solution 1:

I see this every few months and all other features of the device seem to work fine when it happens. The short answer is a restart has always fixed it for me, either from the Airport Utility or if you must by cycling the power.

Solution 2:

Are you connected to the 5ghz wifi or the normal wifi ?

I had the exact same problem you describe, Airport Utility showed nothing wrong, green lights across the board, but when trying to do a Time Machine backup, it wouldn't be able to find the disk.

Additionally, I was also unable to access the Time Capsule's disk through Finder. It shows up alright, but I could not connect.

Manually switching wifi network to the non-5ghz one solved both the backup and Finder problems.