This just in:
I cannot connect to my Linksys WRTP54G (yes, the one that comes with Vonage) using WEP either. Just tried it.
So... not an isolated incident.
Possible solution, cheaper than AP Extreme: buy a cheap wired router, plug an AP Express into it.
Edit: BTW, I can't help but laugh at all the things you did to debug... not because they're wrong, but because of the way you rattled them off - it just shows how many various problems you've been having lately. So, I laughed... but I felt bad for you at the same time.