Reboot the firebox to reset the license count and free up licenses that may not be in use anymore.

I ran into this after changing a DHCP pool for a customer. They had the same number of PCs as before making the change, but they were all at different IP addresses. The firebox continued counting until all the licenses were tied up. Simply cycling the power corrected the issue. Of course you want to warn before knocking down the internet (and any VPN users).

One thing to note: PCs being blocked from web access were stil able to ping across the VPN even though their email and browsers were blocked.