Windows Server 2003 with KB938397 hotfix is not sufficiently tested platform and we are not entirely sure whether the hotfix is supposed to make signature generation work - there is a ver similar KB968730 hotfix that is newer and addresses a similar problem, so installing it first might be a good idea.

To help us in analyzing this, could you please run the following program and let us know what output it displays?

using System;
using System.Text;
using System.Security.Cryptography;
using System.Security.Cryptography.Pkcs;
using System.Security.Cryptography.X509Certificates;

namespace Rebex.Support
{
    class CertificateInfo
    {
    	static void Main()
    	{
    		string subjectDN = "cn=AliceRSA"; // replace this with the actual certificate subject DN

    		// find the certificate
    		X509Store store = new X509Store(StoreName.My, StoreLocation.CurrentUser);
    		store.Open(OpenFlags.ReadOnly);
    		X509Certificate2Collection certificates = store.Certificates.Find(X509FindType.FindBySubjectDistinguishedName, subjectDN, true);
    		X509Certificate2 certificate = certificates[0];
    		store.Close();

    		// display information about the private key
    		RSACryptoServiceProvider rsa = (RSACryptoServiceProvider)certificate.PrivateKey;
    		CspKeyContainerInfo info = rsa.CspKeyContainerInfo;
    		Console.WriteLine("Accessible: {0}", info.Accessible);
    		Console.WriteLine("HardwareDevice: {0}", info.HardwareDevice);
    		Console.WriteLine("KeyContainerName: {0}", info.KeyContainerName);
    		Console.WriteLine("KeyNumber: {0}", info.KeyNumber);
    		Console.WriteLine("MachineKeyStore: {0}", info.MachineKeyStore);
    		Console.WriteLine("Protected: {0}", info.Protected);
    		Console.WriteLine("ProviderName: {0}", info.ProviderName);
    		Console.WriteLine("ProviderType: {0}", info.ProviderType);
    		Console.WriteLine("UniqueKeyContainerName: {0}", info.UniqueKeyContainerName);
    	}
    }
}

We will try to test this ourselves as well in the next few days.