I recently had a problem getting STARTTLS working on exim4 on Debian 4.0 (Etch). It kept reporting:
TLS error on connection from host (ehlo) [ip]
(cert/key setup: cert=/etc/ssl/certs/whatever.crt key=/etc/ssl/private/whatever.key:
Base64 decoding error.
This was confirmed by running gnutls-serv --debug 5 --x509certfile foo.crt --x509keyfile foo.key, which reported the same error.