The fact that you get a different certificate behind this proxy within this network and without this proxy seems to indicate that this is an SSL-inspecting proxy (or "MITM proxy").
A proxy server like this is able to look into the encrypted SSL/TLS traffic by impersonating the target server. They do this by generating their own certificate, replacing that of the genuine server. Such a certificate is issued by a CA embedded within the proxy server (which may be able to generate the certificate dynamically). Such certificates are recognised by the workstations within the company network (or similar, wherever that proxy server is installed), because these machines have been configured to trust the CA certificate of the proxy server in addition (or instead of) the default CA certificate list provided with the OS or browsers.
(You could see this as a "legitimate MITM attack", which isn't actually an attack, since the trust in that extra CA certificate must have been approved by the local policy makers and set up by the system administrators.)
It's very likely that the installation on that CA certificate was done by your sysadmin team on the Windows machines, but your Ubuntu machine might have been left out (very likely if you've installed it yourself). It's not about the proxy server not being able to identify your system correctly; rather it's your system that's not configured to trust your proxy server.
You'd need to install that CA certificate yourself on your machine and in your browser. You could ask your network team for that CA certificate, or you should be able to export it yourself from a Windows box: look at the issuer cert for any of the website you visit from a machine where the connection works (usually accessible with something like "view details", depending on the browser you're using there), export it (PEM/Base-64) and import it on your Linux machine.
You'll need to import it into Firefox as a trusted authority (Options/Preferences -> Advanced -> Encryption -> View Certificates -> Authorities -> Import... and tick "trust this CA certificate" for identifying web sites). Other applications have different CA certificate repositories: it may be useful to make a copy into /etc/ssl/certs/ too.
Of course, the result is that whoever is in charge of that proxy server will be able to look at the traffic you're exchanging on any HTTPS site you're using from that network, but that's already the case from any Windows machine configured this way anyway.
