[Mon Dec 20 16:18:20 2010] [error] [client xx.xx.xx.xx] Re-negotiation request failed
[Mon Dec 20 16:18:20 2010] [error] SSL Library Error: 336068931 error:14080143:SSL routines:SSL3_ACCEPT:unsafe legacy renegotiation disabled
Googling around I finally found this post in the openssl-users mail archive which described the problem. Apparently the latest openssl package fixes a renegotiation bug which allowed a man-in-the-middle to intercept negotiation traffic. This was fixed by extending the ssl protocol. Some browsers like IE 7 and 8 and Safari (!) however still do not support this new extension so cannot connect over ssl anymore to the server.
In the Apache server a new option was added (SSLInsecureRenegotiation) which allows you to disable this bugfix so older browser can still connect. This means however that you are still vunerable to man-in-the-middle attacks !