Code signing with signtool fails due to private key filter

While trying to sign some installer created by the company I am working for I encountered an error, which I have not been able to solve. I am using the same certificate which has been used on another machine (Win7) successfully in the same way for signing quasi the same installer. Anyway, on our Windows Server 2008 which is running CruiseControl.net I tried to sign an installer with signtool.exe and it fails with the following error:

The following certificates were considered:
    Issued to: <our company>
    Issued by: <some ca>
    Expires:   <is valid>
    SHA1 hash: <...>

    Issued to: <...>
    Issued by: <...>
    Expires:   <...>
    SHA1 hash: <...>

After EKU filter, 1 certs were left.
After expiry filter, 1 certs were left.
After Subject Name filter, 1 certs were left.
After Private Key filter, 0 certs were left.
SignTool Error: No certificates were found that met all the given criteria.

I tried installing the certificate to different certificate stores, tried different versions of signtool.exe and tried to use the .cer file directly, but it made no difference. I am receiving the error mentioned above in all of the cases. I tried the following command line commands

signtool.exe sign /debug /n "MyCompany" C:\my\installer.exe
signtool.exe sign /debug /f C:\path\to\my\certificate.cer C:\my\installer.exe

but I left the /debug away in some cases. Is there anything I am doing wrong or missing?