virtualbox.org

I have 4 Fedora Guest - 2 are 10 and 2 are 11. When they reboot ( new kernal or for testing options ) the network appears to be working in Linux but It cannot ping outside or be pinged from outside but it pings itself with no issues. I tried both virtual ethernet types with no differences.

But if I login as root and run service NetworkManager restart and wait 10 second it sometimes will work and i can ping outside - It sometimes takes 3 tries. I have 2 bridged ethernets, one that can see the outside world and one that can see my private computers.

Also there need instructions to state that if a new Linux Kernal is built, you have to reinstall the guest addition to get them to work after you reboot into the new kernal.

Yup!
Section 4.3. Linux Guest Additions explains it for you.
But I don't think that is your problem. I had this too on Fedora 10, where I need to stop the network and then start it again for it to work. Fedora 11 does not seem to have this problem as much though at least for me. I think it has to do with the network manager as I have read a lot about people complaining about it. I turned mine off and set up the network manually and fixed the problem all together.

True, NM can give you a lot problems. I don't use it, because I just don't like the way it works with my wireless and all (either you're in roaming mode where you switch SSID easily, or you're stuck on one network because it uses static addresses). For me, setting the network manually using the config files, or use WICD network manager solved a lot of annoyance that NM caused.