Hey All,
Started getting this message yesterday on a 1.3.9h install (yeah I know right).

After reviewing various threads here I ran up vanilla v1.5.5a install, configured the PP Express Checkout and got exactly the same error, so I'm guessing that it's pointing at the hosting provider.

So far I have not got anywhere yet with the hosting provider nor PayPal, so at this stage I just wanted to post a couple of useful links I found.

Information About the Changes
Announcement: PayPal SSL Certificate Upgrade Microsite
Link: PayPal SSL Certificate Changes

Hoping to make some further progress soon, and will post here for prosperity.