I had the same problem and although I was already using an SSL server, simply changing the links to https wasn't working as there was an underlying problem.
That highlighted bit told me that we should be given the option to trust the certificate, but since this is the app store, working through Safari that recovery suggestion just isn't presented.
I wasn't happy with the existing solutions because:
I finally found a solution by creating a Self Signed Root Certificate Authority and generating our server's SSL certificate using this.
I used Keychain Access and OSX Server, but there are other valid solutions to each step
From what I gather, certificate authorities are used to verify that certificates are genuine. Since we're about to create one ourselves, it's not exactly secure, but it means that you can trust all certificates from a given authority. A list of these authorities is usually included by default in your browsers as these are actually trusted. (GeoTrust Global CA, Verisign etc)
In our case, certificate signing requests are generated by the server admin. Simply it's a file that asks "Can I have a certificate with this information for my site please".
Acting as the certificate authority again, it's up to you to decide if the person who sent you the CSR is genuine and they're not pretending to be somebody else. Real authorities have their own ways of doing this, but since you are hopefully quite sure that you are you, your verification should be quite certain :)
You can click continue through the rest of the options.
The Mail app will open giving you the chance to send the certificate. Instead of emailing, right click it and save it.
We now need to set up the server to use the certificate we just created for it's SSL traffic.
Each device you need to install apps on will need to have a copy of this certificate authority so that they know they can trust SSL certificates from that authority
Make sure your plist links are https