CCurlFile::Stat – Failed: SSL connect error(35)

Ubuntu 16.04, Kodi 16.1 GIT:c327c53 using PlexKodiConnect 1.5.1.

Setup has been working for some time now, but since a couple of days I am unable to get new cover art. During my debugging attempts I completely removed the plexkodiconnect configuration and resynced, which results in no cover art at all. The kodi log fills itself nicely with the following errors:

Code:
22:42:16 T:140018316990208   ERROR: CCurlFile::Stat - Failed: SSL connect error(35) for https://MyIPandIdentifier.plex.direct:44443/library/metadata/475206/thumb/1484860451?X-Plex-Token=ThisIsMyToken

I have tried installing a new curl from the yakkety (17.04) repositories, but that gave me the same problem. I also completely removed my kodi user home directory and restarted with a new profile. Same problem as well.

If I check the link on the command line or a browser, it resolves and gives my a nice picture.

Completely stuck on how to debug this, read most of the older threads, but to no avail. Any ideas?