Time Capsule still provides Wi-Fi but is not discovered by AirPort Utility
Follow these steps and it should be OK:


Press the reset button on the Time Capsule.
Forget the old time capsule in Airport Utility.
Re-add the reset Time Capsule.
Update the Time Capsule's firmware.


The Back to My Mac function caused it to be not seen by the Airport Utility despite it working fine otherwise.