So after poking around with it, I settled with this:
First I looked up what DNS the server uses:
~$ nslookup
> server
Default server: 4.2.2.1
Address: 4.2.2.1#53
Default server: 4.2.2.2
Address: 4.2.2.2#53
Then added to the server.conf
push "dhcp-option 4.2.2.1"
push "dhcp-option 4.2.2.2"
Apparently windows must be spoonfed with a DNS, whilst Ubuntu can find its own way...