Websense blocking random sites.

We are a school district, with a WebSense content filtering package (version 5.3). we have had this product for years without any issues.
Websense is sitting off our Pix firewall (Version 6.3(1))
In the past day we started experiencing a very weird problem.

Randomly, sites get blocked, though we wouldn't get the Websense Blocked page, but rather a page timeout.
Observations I have made over the process:
- Google.com is one of the sites that was blocked. however,  I can get to google by its IP address
   - I have restarted our DNS services, and Update the server files, and thoroughly tested DNS. I am able to resolve all addressed immediately without a problem.
- I was able to telnet to google.com to port 80 without a problem (even by URL).
- That same morning, our district website, which is a hosted website was not available due to Websense malfunctioning, after rebooting the server though the other inaccessible URLs (i.e google.com) remained inaccessible, the district website became accessible again.
- When restarting the Filtering service, and WHILE the Websense database is loading, everything works just fine (Even google), AND, filtering IS functional.
   - As soon as the database finishes loading, all the URLs that used to previously be inaccessible, become inaccessible again.

Things we've done:
- Restarted the services, and websense server multiple times
- Changed the setting for DNSLookup to AUTO, ON and OFF in EIMServer.ini, thinking it may be a DNS issue.
- Ran a repair on WebSense, and forced a redownload of the database.
- Called WebSense support, and reached Level 2 support, and they were stomped by the problem.
   - They suspected it's my DNS (I don't agree, as all DNS resolutions are working perfectly)
   - They suspected it's my firewall (I have 2 interfaces on my WebSense box, one connected to the network, and the other directly connected to the DMZ interface on the firewall, to avoid traffic lag.) This has worked for years without any issues, so not sure why this would just now become a problem.    -
 
Things I know:
- The box that my Websense is running on is underspec-ed (800Mhz with 1Gb of RAM). But has been running that way for the past 4 years.
- Two things have changed this year was that we upped the user count from 2500 to 4000, and we changed most of our sites from ATM to TLS connections.  

At this point, we are completely stomped as to what is causing it.
Websense wanted us to call a conference with us them, and Cisco TAC, which didn't make sense to me
The next steps I'm working on are:
1- This afternoon, will run SFC on the Websense host OS, as well as defrag, as the OS is in pretty bad shape.
2- Placed an order for a new server to move the Websense service to.

All that being said,  would anyone have any ideas about why this problem may be occuring?
If you need any more information that I may have omitted, please let me know and I'd be happy to provide it.