I've disabled IPv6 on both computers - but doesn't IPv6 make it easier for Airport to function?
Some folks have reported problems with connecting to certain sites when IPv6 is enabled. Since disabling it didn't resolve the problem you're having, you should go ahead and re-enable it.
In the end, it is still the same situation. There must be a simple explanation to this - at least I hope so! Any help is appreciated.
It's possible that the AEBS may need to be reset back to it's "out-of-the-box" condition, since you are still not having any luck connecting with any level of encryption. To perform a "hard" reset:
http://docs.info.apple.com/article.html?artnum=107451
It also could be a communication problem between the modem and the AEBS, you may want to consider doing a power recycle to try to resolve this.
Modem/Router Power ReCycling
- Power-off the Cable modem, AEBS, & iMac. (If possible, leave the modem off overnight.)
- Power-on the Cable modem; Wait at least 30 minutes.
- Power-on the AEBS; Wait at least 5 minutes.
- Power-on the computer(s)