The reason I suggested web shield settings as a (remote) possibility to look into is because the latest stable web shield version (6.0.1xxx) was blocking more internet traffic than just web browsers, and some reports were somehow strange.
Changing the setting and testing it is so simple and fast that it was worth mentioning.
Deleting the firewall rules would take longer than the web shield change
, but it is still relatively easy to test.
Besides those, you could try temporarily disabling shields one at a time (including mail shield specifically) and see if the behavior changes.