So you have a Time Capsule in the network, but not available on the computer.
This is a standard problem with Lion. The internet is working through the TC but it refuses to recognise it as a backup location. I don't have a solution.. usually a simple restart of the TC gets it recognised, but not for very long.
Is TC working in bridge or router mode?
You are connected by wireless? Can you try ethernet?
Have you ever backed up before? Was this working and failed or a new setup?
Wireless setup is plainly more of an issue.
Make sure you download 5.6 utility for Lion.
Set up the TC again, changing all names to simple no spaces no special characters.. this is both TC name and wireless.. eg name of the TC.. TCHome.. name of wireless 2.4ghz.. TC24.
I also recommend different name for 5ghz.. eg TC5
Manually set wireless to N.. and set the channel for 2.4ghz, choosing one out of 1, 6, 11
5ghz you can pick any channel really but 40 is kind of default.
I strongly recommend first backup by ethernet.. even if it means unplugging the TC from the network so you can place it next to the computer. That speeds up the backup by 3-4 times.