This is a weird one.

Installed BMEE 3.5 and random users get the "403 forbidden" error
stating that the ACL is preventing them from accessing the site.

NOT the "not logged in" error.

The CLNTRUST.EXE is running and the "stats" show requests are going
through okay.

Random pc's, and random users.

Meaning, user in the "internet" group may be able to surf the internet
at times, and at other times it won't let them.

My initial suspect would be licensing (maybe for some reason it's
running out of licenses for proxy?) but you'd think you'd get a
different error.

UserA logs onto PC-1. Cannot surf the internet.
UserB logs onto PC-1. CAN surf the internet.
UserA logs back onto PC-1. CAN surf the internet.
UserB logs onto PC-1. CANNOT surf internet

random like that (not necessarily in a consistent on again/off again
order).

Any ideas what log files to look at to start figuring out what's going
on?

Win98 AND WinXP are affected. I know it's not the firewall because it
DOES work (sometimes) on XP.