Exim DKIM Error: DKIM: signing failed (RC -101) no matter what private key I try

I have this problem with Exim. DKIM fails on signing outgoing mails.

This is the /var/log/exim4/mainlog output (Debian Squeeze):

2012-08-02 17:11:33 1Sx1k5-0004Tk-9D <= me@my_domain.com U=me P=local S=399
2012-08-02 17:11:33 1Sx1k5-0004Tk-9D DKIM: signing failed (RC -101)
2012-08-02 17:11:33 1Sx1k5-0004Tk-9D => somebody@gmail.com R=dnslookup T=remote_smtp H=gmail-smtp-in.l.google.com [173.194.77.27] X=TLS1.0:RSA_ARCFOUR_SHA1:16 DN="C=US,ST=California,L=Mountain View,O=Google Inc,CN=mx.google.com"

The version of Exim running is:
Exim version 4.72
Berkeley DB: Berkeley DB 4.8.30: (April 9, 2010)
Support for: crypteq iconv() IPv6 GnuTLS move_frozen_messages DKIM

As I've readed here:

Hey Jon,
The error: “DKIM: signing failed (RC -101)”
is the error code PDKIM_ERR_RSA_PRIVKEY (from src/pdkim/pdkim.h)

/* Function success / error codes */
#define PDKIM_OK 0
#define PDKIM_FAIL -1
#define PDKIM_ERR_OOM -100
#define PDKIM_ERR_RSA_PRIVKEY -101
#define PDKIM_ERR_RSA_SIGNING -102
#define PDKIM_ERR_LONG_LINE -103
#define PDKIM_ERR_BUFFER_TOO_SMALL -104

and is only returned in one place – in src/pdkim/pdkim.c

/* Perform private key operation */ 
if(rsa_parse_key(&rsa, (unsigned char *)sig->rsa_privkey,
strlen(sig->rsa_privkey), NULL, 0) != 0) {
return PDKIM_ERR_RSA_PRIVKEY;
} 

So it looks like there is a problem parsing
the RSA key that you generated for Exim. This could be because the key
generation failed, or because exim doesn’t have access to the file
(file permissions). I would start by trying to re-generate your
certificates.

So the problem is in the private key.

I've tried generating different keys but no matter what private key I use, Exim still logging: DKIM: signing failed (RC -101).

I've tried:

# openssl genrsa -out dkim.private.key 768

then

# openssl genrsa -out dkim.private.key 1024

then

# openssl genrsa -out private.key 768

or

# openssl genrsa -out private.key 1024

even I've tried this DKIM Key Generation Wizard
but the error is still there.

This is the Exim config section for DKIM (from /etc/exim4/exim4.conf.template):

remote_smtp:
  debug_print = "T: remote_smtp for $local_part@$domain"
  driver = smtp

  dkim_domain = my_domain.com
  dkim_selector = dkim
  dkim_private_key = private.key
  dkim_canon = relaxed

the keys I'm using are in /etc/exim4 to avoid permissions issues

Has anyone any idea? How can I solve this and get my outgoing mails signed