[ran-o-matic]

To reason to disable WEP is to isolate the problem. Right now, I don't think anyone could tell you what is wrong with your system, but it does seem clear that the problem is unique to what you have. You need this test to confirm your own theory that it is WEP related.

The thought that you have a DNS issue (from computercarl in post #4) is possible, but right now I'm assuming the you have a simple network and depend on Verizon for DNS.

Wait a minute - You're using NAT so that you have private addresses on the inside of your network, right? What is your inside address range? Any change you are using a publicly routable address range? That would cause you some grief.