Another update:
I noticed that once the problem started, it created a cascade effect across the network where any iDevice + systems with Lion could not connect to it wirelessly. Day 1 my MacBook Air couldn't connect... Day 2, my iPhone, iPad and Daughter's computer (with Lion) couldn't connect. I had to reset the router (unplug it, wait and replug it in).
Since then, for six days, all was fine.
Today, I suddenly lost connection on my new MBA again. Same symptoms... searching for network and unable to connect. It asked me for a password and I put the right one in. It told me "invalid password".
I went and reset the router again... and now it's fine. MBA connected without issue immediately.
Looking at a calendar, I realize it was last Sunday I started having the first problem... and now again this Sunday. I wonder if my ISP is resetting my connection on Sundays, and if the systems with Lion are for some reason having an issue with getting a new IP address... hmmm.
Will have to wait a week again to see! LOL
It's definitely a new problem since the MBA entered our house. My daughter got a new iMac around the same time too. I've never had a problem with my Time Capsule like this before... it's been solid for a long long time.