The Firewall is running just fine. Nat Service will just stop. As soon as I start the Service again it will run anywhere from 5 - 15 min then just stop again.
You may have a preset cache that when it fills up, it has no more room for you to surf the net. I don't have the tools available to see if there is a menu to setup caches and that, but I bet that's probably the problem.