I went out after the post and suddenly realised that I had only tried on saturdays, when the mail checks all day. I switched the mail to offline, tried again and it worked!
So yes, it was the same thing as you had said.
Would have been nice if it said why it couldn't connect!

Thanks for the info