Tive esse mesmo problema em um cliente.
Fiz esse hotfix aqui esse 2 procedimentos abaixo.
Pessoal é muito simples de se resolver:
1° Passo - Atualize o Windows Server 2003 para o SP2 (se estiver com o SP1 não irá funcionar), reinicie o servidor.
2° Passo - Instale o HOTFIX (http://support.microsoft.com/kb/968730) correspondente a tua versão do Windows Server ou seja 32bits ou 64bits, reinicie novamente o servidor
3° Passo - Instale os certificados
4° Passo - PRONTO é só testar agora.
E tambem
Em relação ao seu problema, terá que desabilitar uma informação para que possa os usuarios poderem validar via WEB. o caminho é:
Painel de controle >> adcionar ou remover programas >> adicionar/remover componentes do windows >>
Na lista dos componentes, procure " Configuração de Segurança reforçada da Internet Explorer " e click em "Detalhes"
Desmarque as opções " Para Grupos de administradores " e " Para todos os outros grupos de usuários"
Depois OK, e terá que reiniciar seu servidor para que possa validar esta guia!
Tiradas do post
http://social.technet.microsoft.com/Forums/pt-BR/94c4a64d-c656-4ba5-ab64-333af1c0eac4/certificado-digital-a1-v2-no-funciona-no-windows-2003-server?forum=winsrv2003pt
Espero ter ajudado.