There seems to be an issue with Android 4.3. and the firewall.
On the Galaxy Nexus i9250 with Android 4.3 (build JWR66V) internet access is only granted, if firewall logging is activated.
At least some apps, like K-9 Mail, only can access internet with actice logging.
This appears as well over WLAN, as over 3G - both are allowed.
Firewall is in whitelist mode.
Im found this in Avast! 2 and changed to version 3.0.5718, where this problem still is present.
Workaround of course is activating the firewall log.
This seems a problem in combination with Android 4.3, as everything was fine in Android 4.2.
Other firewalls - like droidwall - show the same problem.