Yes this is exactly the problem but the error is specific to SSL3 shared ciphers.
routines:ssl3_get_client_hello:no shared cipher
You may also want to add this
ssl_cipher_list = ALL
Basically you should focus as to why SSL3 ciphers are not activated. If the above parameter did not work, it is very possible the openssl distribution you have has not included SSL3 support at all. You may have to do some recompiling if this is the case.
If your old clients are only from your internal net and you do not provide any ISP like services you may consider upgrading the clients as you will have quite often issues such as this one in the near future as SSL3 support and below is in the process of being dropped from almost everything.
Thank you for your input and everyone elses.
You may be right that any solution wouldn't have much longevity - so we will just tell the affected users that older clients are not supported any longer.