Pessoal... Gostaria de agradecer a todas as ajudas que tive aqui. Consegui resolver o problema.
No fim identificamos que havia uma das Tags do XML que estava com os dados errados, mais precisamente a tag com os dados do Prestador.
A mensagem que me foi passada pelo provedor não tem indicação do que poderia estar gerando esse erro. Como ela informava apenas que o certificado deveria ser no padrão ICP e etc, não era sugestiva e nos levou a acreditar que era problema realmente no certificado.
Enfim... erro solucionado, caso tenham alguma dúvida e eu puder ajudar estou a disposição...
Obrigado a todos!