You say that you've cleared the history, but have you cleared the cookies?
If not, then try : right click on the page once you receive the error, select "Page Info", select "Security", and then select "View Cookies".
From there you can remove individual cookies or all of them.
The other thing to check would be your network settings, specifically Proxy Settings. From the Top Pulldown, select Tools>Options. The select "Advanced" Then "Network". Once there, select "Settings". Use the "System Proxy Settings".
If your system uses a proxy server for internet access, it should have the proxy server configuration on a lower level and generally Firefox should not override that.
I hope this helps..