Olá,
Enfrentei o mesmo problema para o município de Mossoró - RN e, verificando o WSDL do webservice (http://www.tinus.com.br/csp/mossoro/WSNFSE203.Service2.nfseSOAP.cls?wsdl=1) identifiquei que devem ser informados os campos ADNCodMotivo e ADNMotivo, além de ADNChave, conforme exemplo abaixo:
<Pedido>
<InfPedidoCancelamento Id="cancelamento:2600000000521">
<IdentificacaoNfse>
<Numero>2600000000521</Numero>
<CpfCnpj>
<Cnpj>****</Cnpj>
</CpfCnpj>
<InscricaoMunicipal>****</InscricaoMunicipal>
<CodigoMunicipio>2408003</CodigoMunicipio>
</IdentificacaoNfse>
<CodigoCancelamento>1</CodigoCancelamento>
<ADNChave>*****</ADNChave>
<ADNCodMotivo>1</ADNCodMotivo>
<ADNMotivo>Teste emissao e cancelamento.</ADNMotivo>
</InfPedidoCancelamento>
<Signature xmlns="http://www.w3.org/2000/09/xmldsig#">
<SignedInfo>
<CanonicalizationMethod Algorithm="http://www.w3.org/TR/2001/REC-xml-c14n-20010315" />
<SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#rsa-sha1" />
<Reference URI="#cancelamento:2600000000521">
<Transforms>
<Transform Algorithm="http://www.w3.org/2000/09/xmldsig#enveloped-signature" />
<Transform Algorithm="http://www.w3.org/TR/2001/REC-xml-c14n-20010315" />
</Transforms>
<DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1" />
<DigestValue>****</DigestValue>
</Reference>
</SignedInfo>
<SignatureValue>****</SignatureValue>
<KeyInfo>
<X509Data>
<X509Certificate>****</X509Certificate>
</X509Data>
</KeyInfo>
</Signature>
</Pedido>
