For the Layer 2 FW policy I verify that you are using Layer 2 Firewall Inspection template based policy. With the template inspection is turned on. Additionally rule ID 1 allows DNS from firewall itself.
The problem sounds like firewall is trying to reach servers to query for category and thus delaying connection heavily when waiting for timeout. If you log in to engine you should see among established connections firewall having established connection to port 2316 on server (#netstat -an | grep 2316). You can also try to ping "service.brightcloud.com", requires policy to allow ping from firewall.
If license would not be including the feature you would get validation warning telling web filtering to be ignored on policy install.
Hope this helps at least to verify whether the nodes have connection to category server or not.
I've testes connections from firewall to brightcloud:
tcp 0 0 192.168.1.10:18766 18.104.22.168:2316 TIME_WAIT
tcp 0 0 22.214.171.124:7474 126.96.36.199:2316 ESTABLISHED
tcp 0 0 192.168.1.10:18769 188.8.131.52:2316 TIME_WAIT
tcp 0 0 192.168.1.10:7473 184.108.40.206:2316 TIME_WAIT
I've tested new evaluation license - all features enabled - the same problem. I've tested the same policy in my lab (this time policy was installed on MFE s1104 - firewall in L2), everything works - magic ....
ICMP to service.brightcloud.com is blocked.
Please check /data/diagnostics/urlcatd.log for any relevant errors.