Found the problem and solution, although I'm not very happy with the solution...
It appears that Evolution needs NetworkManager, which I've disabled to be able to configure my network from command-line. This is what Evolution's FAQ
If the problem persists and you are sure you haven't clicked the icon, but you can still reach the network from other apps on your system (browsers, FTP, Ssh, ping etc.) it may be that NetworkManager (NM) is not properly configured. Many Linux distributions now use NM to manage their connections, and if it's installed Evolution will use it to detect if the network is up.
I've enabled Network Manager (NM_CONTROLLED=yes) and Evolution downloaded my mail in a snap (oh, after I had to reconfigure the DNS's again ).