Odds are this problem has nothing at all to do with X, instead it probobly has to do with how lynx finds DNS information.
The first thing I would check is what happens when you start pinging random domains. It should say something like this:
$ ping google.com
PING google.com (22.214.171.124) 56(84) bytes of data.
64 bytes from py-in-f99.google.com (126.96.36.199): icmp_seq=1 ttl=240 time=29.4 ms
That way I would know I was getting DNS information, but the fact that one of your browsers works, reguardless of which(x or not), indicates that you are getting good DNS information. For some reason your other browsers aren't using that good DNS information I guess.
I would try setting my DNS servers manually. I use http://www.opendns.com/
the addresses are 188.8.131.52 and 184.108.40.206
set them with nameserv ###.###.###.### in /etc/resolv.conf
Depending on distro, if you use DHCP that file might get overwritten in which case you would have to edit /etc/dhcp3/dhclient.conf I think.
I actually have those DNS addresses set in my router so I get them through DHCP because with all my computers it's just easier that way.
If all that is way too complicated you could just set your DNS servers in the individual browsers.