Question : Undeliverable email & ping could not find an external host

What would cause SMTP outbound traffic and pinging any external web/IP address to fail? (ie. ping www.google.com = "Ping request could not find host www.google.com."

Several gremlins and changes have happened in our system over the last 5 days.  
1.We have changed our domain web host. - the mx record has been verified that it is pointed to our external IP address.  We are receiving e-mail.
2.Our firewall device has failed, been worked on, and is working properly now. - SPAM Filter is working much better than before all these problems.
3.Over the weekend (while the firewall was down) I explored several areas of the Server - DSN, DHCP, Routing and Remote Access, Services -  trying to get us up and running again - to my knowledge I don't remember changing anything significant that would affect the problems we are having - BUT I wouldn't rule it out.

I just don't know where to go with this problem.  I've tried numerous things on my own - but I'm just not smart enough for this problem.

ps. what is strange about the whole thing is 1. we can receive e-mail, 2. we can surf the internet through the proxy/firewall and active directory roles are working just fine.

Answer : Undeliverable email & ping could not find an external host

Problem solved!

After many hours of tech-support through many different sorces - I solved the problem myself.

The issue was the firewall, but here is the catch that no one understands why it worked.  We simply unplugged and bypassed the firewall straight to the internet (made the appropriate gateway changes), got it working, then re-plugged into the firewall and everything started working again.  After all that work - unplug and replug was the solution.  Sorry for wasting everyone's time.

Thanks all for the attempted help.