@PatchesTheCaveman:
Thanks, changing the DNS servers worked. Still, it is a bit weird that the problem only showed up under Ubuntu. Marking Solved.

In case anyone is confused the solution follows:

1. Change DNS server(s) in network.*
2. reboot**

* In my case I used Google's public DNS as provided by PatchesTheCaveman

** I suspect this is not strictly needed, but I could have stopped/restarted network connections; rebooting is so Microsoft. I should really learn to manage my box better.