Turns out the message "A Ubisoft service is unavailable at the moment." is way off. In my case, it had absolutely nothing to do with a service being unavailable, connectivity was perfectly fine.
The uplay client is just not getting the response it's expecting.
The reason I claim this is because I remembered I had a second account with which, to my surprise, I was able to login to the uplay client just fine. Let me refer to my accounts as "Account A" with which I couldn't login and "Account B" which magically let me login into the uplay client.
When I logged in with "Account A" on the uplay website there was an error stating "countryCode is not ISO-3166-1". I initially ignored this since the whole website is buggy and clicking "Ask me later" got me to my account page. But when I noticed I didn't get the message when logging in with "Account B", I got suspicious. For "Account A" I made the mistake of selecting the wrong country when I signed up with it, "Netherlands Antilles" when I actually live in "The Netherlands".
After contacting support, asking them to change my country (something you can't do through your account settings ...) to "The Netherlands" I was finally able to login with both Account A and B into the uplay client.
If you're wondering why I really wanted my "Account A" to work, it's because I was able to activate and play ACII with "Account B" exactly once. When I booted the next day, to play some more ACII with "Account B", I received a pleasant "This CD Key or Activation Code is already in use with another Uplay Account". Turned out the game was, somehow, activated for "Account A". So I really wanted that account to work.