Pedro,
Estou com problema em todos os métodos na verdade. Também estou utilizando C# aqui, e a maneira como assinava anteriormente não está funcionando neste novo WebService. Já tentei assinar o XML todo, assinar apenas o nó onde tem a assinatura e nenhum deles funcionou.
Em resumo, gerei as classes em C# à partir do XSD, utilizo elas e converto para um XMLDocument. Após isso, utilizo a classe SignedXml para gerar o XML assinado e enviar ao servidor, não sei se é o mesmo processo que vc está fazendo.
Mas Diego,
Se você conseguir compartilhar o seu código, mesmo que não seja em C#, pode nos dar alguma luz por aqui, ficaria agradecido.
O IMA bem que poderia manter um repositório no GitHub com exemplos mais claros e códigos para as principais linguagens.