Access to this Site Denied Popups

This problem is actually occuring more frequently at various workstations throughout the Dept. When a user tries to access a webpage (our company or otherwise), the company ‘Access Denied’ webpage appears. Sometimes it appears as a popup, and the desired page still opens in another window, so they can still access it. Other times access really is denied. Does this has something to do with the filtering software (Websense? is what i think we use), on the Internet server, or is it a workstation issue. I’ve done all i can think of (delete history and cache, run updates).