This sounds like a firewall thing. Exactly the same messages I got with my RH 7.0 system. When I looked in netconfig with ppp0 up, it showed my DNS addresses. Temporarily disable firewalling through LinuxConfig, and see if it works. If that's the problem, check http://www.pointman.org
for PMFirewall which does it all for you.