SSL connection errors from Apache
The issue you are having is that intermittently, the signature on the message recieved by the browser is wrong.
This can happen for a very large number of reasons. For instance, you may be experiencing an openssl bug, a hardware failure (bad RAM or CPU), some kind of freak coincidence with your key (astronomically unlikely). Or, you may be experiencing exactly what the MAC is designed to detect: someone may be tampering with your traffic enroute.
Since your certificate is self-signed, go ahead and replace it, restart apache, and continue, just as a troubleshooting step. If this doesn't work, check that you are running the latest version of openssl (or just change the openssl version for the fun of it). If you still get MAC errors, investigate whether you have a hardware failure or network tampering going on.
This part of the error is particularly telling:
OpenSSL: error:04067072:rsa routines:RSA_EAY_PUBLIC_DECRYPT:padding check failed
This indicates that most likely the message has been modified from the version that was signed, and possibly truncated.
First of all, self-signed certificates are often more pain than a cheap SSL cert for end users. I do not recommend using them if you have any kind of public interfacing, or even a large number of internal users. Broswers are increasingly getting strict on self-signed certificates by denying them default trust.
Second, there are several different trust stores on a machine.
Linux uses NSS generally (mozilla), but alternatives browsers may have their own trust stores too.
It is possible for a certificate to have the incorrect OIDs set, etc. We need to see the actual certificate. PKIs do not really have confidentiality for certificates - only for private keys.
Please use http://pkif.sourceforge.net/pitt.html and tell us what errors you have, or don't have.
Thanks.