Had the same problem with a brand new Plesk 12.
Instead of modifying /etc/postfix/main.cf, I just had to copy the freshly created smtpd.pem to /etc/pki/[myhostname].pem (look for smtpd_tls_cert_file directive which is already in /etc/postfix/main.cf)
And it worked perfectly after a "postfix reload".