Did you ring apple support?
You have enough equipment there that you should still have phone support on something or buy applecare on the latest air if you don't already.
Changes to OS seldom fix underlying problems.. particularly if you do upgrade installs.. clean install has some hope of fixing things.. upgrade installs .. none.
The interesting thing is, while Airport Utility doesn't see Time Capsule, I can access the configuration panel using the IP address via File/Configure Other.
Can you give a screenshot of this, as I have no idea of the configuration panel. The only access to the TC setup is airport utility.
We do need a full network listing.
What is the main modem.. make and model?
What role is the modem playing.. is it also a router?
How is the TC connected and what role does it have? ie connected by wireless or wired. It is router or bridged.
Do all the computers get internet access via the TC?
Have you tried manually mounting the TC hard disk?
ie in finder, use top menu, Go, connect to server, and type in the following.
AFP://TCname or TCIPaddress (using the actual name or actual IP address) Test with both if the first fails.
It that fails.. try SMB://TCname
And with Mavericks try
Do any of those work.. once the drive is mounted TM can usually access it.
Do the names on the TC meet SMB rules.. this is now more important since Mavericks uses SMB in preference to AFP.
Please reset to factory your TC.. and on a computer that can access it, reset everything.. use a new name for everything.. TC, and each band of the wireless.
Names to be short, no spaces and pure alphanumeric. Not Apple type names with spaces and strange apostrophes..
Also note the following.
For Mavericks you need 7.6.4 firmware.
For access to the TC you need IPv6 set to local-link on the computer.. that is in both wireless and ethernet, whichever you use. Since Mountain Lion and the new version of the utility all access to the TC is restricted to ipv6.
There is an apple doco about the ipv6 requirement.
Need ipv6 in 6.3 utility