Ugh... well that one was dumb.
So it turns out that in Linux you can check a checkbox in your Network Proxy settings (the system settings) that will use the same proxy for all protocols.
Yeah... don't do that!
Unless, that is, your proxy server supports SOCKS as well as HTTP/HTTPS/FTP (highly unlikely).
It turns out that if you check that checkbox, your proxy server will be registered as a SOCKS proxy and for some reason, websocket connections in both Chrome and Firefox will want to use that. So your HTTP proxy will end up getting a bunch of weird SOCKS handshakes that it doesn't understand and any websocket connection will fail.
This was tested on both Ubuntu and Kubuntu and the "problem" exists on both.
TL;DR; Don't check the "Use this proxy server for all protocols" checkbox unless your proxy server supports the SOCKS protocol. Instead, manually fill in the same server for the different protocols (http, https and ftp) but leave the socks protocol empty (or point to an actual socks proxy server).