Hmmm... Interesting problem.
I think you basically need to go back and start diagnosing the problem from the lower levels up.
Firstly, what is the output of attempting to ping an external host?