How does the server know what certificate the document is signed with? You seem to not to include the cert in the signed document:
KeyInfo keyInfo = new KeyInfo();
KeyInfoX509Data keyInfoData = new KeyInfoX509Data( Key );
keyInfo.AddClause( keyInfoData );
signedXml.KeyInfo = keyInfo;
If you need more details, consult my blog entry
http://www.wiktorzychla.com/2012/12/interoperable-xml-digital-signatures-c_20.html