Solution 1:

Have you checked the file permissions for

smtpd_tls_session_cache_database = btree:${data_directory}/smtpd_scache
smtp_tls_session_cache_database = btree:${data_directory}/smtp_scache

Are these files being created?

What happens if you temporarily disable those lines?

Also try increasing the log level to 3 or 4.

EDIT: These are additional lines I added to master.cf (postfix 2.5.1):

# TLS stuff
smtps     inet  n       -       y       -       -       smtpd -o smtpd_tls_wrappermode=yes -o smtpd_sasl_auth_enable=yes
submission inet n       -       y       -       -       smtpd -o smtpd_enforce_tls=yes -o smtpd_sasl_auth_enable=yes
scache    unix  -       -       n       -       1       scache
discard   unix  -       -       n       -       -       discard
tlsmgr    unix  -       -       n       1000?   1       tlsmgr
retry     unix  -       -       n       -       -       error
proxywrite unix -       -       n       -       1       proxymap

Solution 2:

This is the way to test STARTTLS with your smtp server:

openssl s_client -starttls smtp -connect yourserver.example.com:587