We discovered the cause of the error. We are using Plesk 12.5 on Debian.
PHP cURL is not using an updated set of root certificates to verify server certs.
Around early September 2014, Mozilla removed the trust bits from the certs in their CA bundle that were still using RSA 1024 bit keys. This may lead to TLS libraries having a hard time to verify some sites if the library in question doesn't properly support "path discovery" as per RFC 4158. (That includes OpenSSL and GnuTLS.)
Download the cacert.pem file from the main curl website [external links are visible to admins only] .
Add the following into php.ini or add into 'Additional directives' under Websites & Domains > PHP settings :
curl.cainfo = /var/www/vhosts/WebSite.com/httpdocs/cacert.pem
Voila it now all works.