If a the new certificate does not match the current private key running on the system, both the correct key and the new certificate need to be uploaded to the appliance at the same time.
The certificate can be verified from the command line with
/gui/dsweb/System/system_master/verifySSLFiles.php '/etc/pki/tls/private/localhost.key' '/home/admin/southern/Your_New_Certificate_Here.pem'
If the certificate is already in PEM format but this error is received, upload both the certificate and its matching private key at the same time to resolve.
The restart of the HTTPd service on the SA appliance may take up to 5 minutes. Also, the help pages are very clear on how to do this from the CLI and the GUI.