podes usar el google sin https el comun el http digamos, es raro, que te de ese erro
http://www.google.com y no
https://www.google.com
tendrias que ver si no tenes un proxy en la red, que casualmente este (mal configurado y cachee https) o actualizar los navegadores, quiza esten obsoletos, o limpiar temporales (cookies) de los navegadores, si estas en win con algo como el ccleaner,
podrias intentar con otros sitios que usen el https y ver
pd
este te puede dar info
http://www.lagado.com/proxy-test tiene la seccion adicional, la del cache test, yo uso squid en la red, y lo tengo transparente y no detectable , no me dice el proxy, pero si me puedo dar cuenta porque el codigo no cambia.
tambien podes mirar en las opciones del internet explorer si no esta configurado para buscar un proxy en la red