Time Machine doesn't see Time Capsule

Recently got a Time Capsule and set it up. It was painless to get the wireless network up. My Mac (and even my old PC) recognizes it without problems. They are now wireless and happily sharing the internet connection.

Now I'm trying to set up Time Machine to do backups, but the Time Capsule is not showing up anywhere. Not on my desktop, not under Devices, and not in Time Machine when it scans for drives to use.

Google searches yield no relevant results, and there is no mention in the manual about how to use it for backups, only how to set up the wireless network. Maybe it is assumed that it's too simple to require explanation - fine assumption unless the device won't even show up!

Please help?

Thank you, Skorpien! I will try those suggestions when I get home and post the results.

So far, no luck. I launched AirPort Utility and for some reason TC won't even show up now. Tried turning it off and on again and re-scanning. Tried resetting TC by putting a paperclip in the magic hole and then re-scanning. No joy.

So I'm now worse off than before and I haven't even changed any settings since last time! (I'm connecting to the internet on somebody else's WiFi network right now.)

Update

I'm back to being able to connect to the internet through my TC. I had to manually choose my wireless network from the OS X menu bar and then rescan. Seems backwards, but it worked.

Some progress was made with Time Capsule's drive as well. It now shows up in Finder under "Shared Devices". (It shows up whether I'm using the 8-character short name or not, so I don't think that's a problem.)
However, when I click on it, it momentarily says "Connecting..." and then soon after, "Connection Failed".

How now, brown cow?

Success!

It's working!

I did two things:
- A Time Capsule update
- Reset the network password (I think this is what solved it)

I still have to do a backup to fully test it, but I don't expect to have any problems from here on out. Time Capsule is showing up as a drive on my desktop.