Ok, this is really weird!
Here are my settings, that finally made it work:
gnome-settings
chatty settings
However, chatty settings seem to clear the proxy setting every time the modem is restarted (which I do by toggling the kill switch). The proxy setting should be 193.209.134.132:8080