El hecho de que obtengas un certificado diferente detrás de este proxy dentro de esta red y sin este proxy parece indicar que se trata de un proxy que inspecciona SSL (o "proxy MITM").
Un servidor proxy como este puede examinar el tráfico SSL/TLS encriptado al suplantar al servidor de destino. Hacen esto generando su propio certificado, reemplazando el del servidor genuino. Este tipo de certificado es emitido por una AC incrustada dentro del servidor proxy (que puede ser capaz de generar el certificado dinámicamente). Estos certificados son reconocidos por las estaciones de trabajo dentro de la red de la empresa (o similar, dondequiera que se instale ese servidor proxy), porque estas máquinas han sido configuradas para confiar en el certificado de la AC del servidor proxy además (o en lugar de) la lista predeterminada de certificados de la AC proporcionada con el sistema operativo o los navegadores.
(Podrías ver esto como un "ataque MITM legítimo", que en realidad no es un ataque, ya que la confianza en ese certificado AC adicional debe haber sido aprobada por los responsables de políticas locales y configurada por los administradores del sistema).
Es muy probable que la instalación de ese certificado AC haya sido realizada por el equipo de administradores del sistema en las máquinas con Windows, pero es posible que tu máquina Ubuntu haya quedado fuera (muy probable si la has instalado tú mismo). No se trata de que el servidor proxy no pueda identificar correctamente tu sistema; más bien es tu sistema el que no está configurado para confiar en tu servidor proxy.
Necesitarás instalar ese certificado AC tú mismo en tu máquina y en tu navegador. Puedes pedirle al equipo de redes ese certificado AC, o deberías ser capaz de exportarlo tú mismo desde un equipo con Windows: mira el certificado emisor de cualquiera de los sitios web que visitas desde una máquina donde la conexión funcione (normalmente accesible con algo como "ver detalles", dependiendo del navegador que estés usando allí), exportarlo (PEM/Base-64) e importarlo en tu máquina Linux.
Tendrás que importarlo en Firefox como una autoridad de confianza (Opciones/Preferencias -> Avanzado -> Encriptación -> Ver Certificados -> Autoridades -> Importar... y marca "confiar en este certificado AC" para identificar sitios web). Otras aplicaciones tienen repositorios diferentes de certificados AC: puede ser útil hacer una copia en /etc/ssl/certs/ también.
Por supuesto, el resultado es que quien esté a cargo de ese servidor proxy podrá ver el tráfico que estás intercambiando en cualquier sitio HTTPS que estés utilizando desde esa red, pero esto ya es el caso de cualquier máquina con Windows configurada de esta manera de todos modos.
