More updates on the SSL issue. I have the following configuration:
http {

...


ssl_prefer_server_ciphers on;
ssl_ciphers RC4:HIGH:!aNULL:!MD5;
ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
ssl_session_cache shared:SSL:5m;
ssl_session_timeout 10m;

...
}

If I disable the ssl_prefer_server_ciphers, the [crit] errors are gone. On the other hand, I cannot use anymore the RC4. Any idea what could cause this?