A Proxy Server is a computer that sits between you and the internet.
Companies often use a Proxy Server as a "barrier" to the internet, so their staff do not go DIRECT to the internet but via this Proxy Server.
The Proxy Server controls traffic going out the internet and coming in from the internet, and adds a level of security and control.
The Proxy Server can be used to block access to certain sites for example (porn, gambling, shopping etc).
I am not sure why YOU should be getting this message, unless you have a special setup for your internet connection (some home users do use a proxy server to "hide" their internet activity).
It is possible to change Windows settings to use a proxy server, so maybe that option had been set somehow (had you been changing any settings?).
Strange that you were able to get to the internet in safe mode, and it is ok now, so I am not sure what the answer is.
But at least now it has been fixed.