Caros,
Como já foram mais de 10 pessoas me perguntando sobre problema de acesso, resolvi fazer duas observações mais comuns:
1º) Caso... VS 2005 com .Net Framework 2.0.
A classe que o VS cria ao referenciar o WS fica BEEEEM diferente da do exemplo... Nesse ambiente não conseguia fazer o ADD do certificado de comunicação no ClientCertifocates, como sugiro no exemplo e passei a receber erros 403 (conforme relatado por alguns)...
Consegui contornar esse problema, na classe gerada pelo VS que implementa uma interface "SoapHttpClientProtocol" com a referencia ao próprio WS. No construtor da classe, alterei uma propriedade privada "useDefaultCredentialsSetExplicitly" para “True” e uma propriedade pública "UseDefaultCredentials" para "FALSE" , pois credencial padrão continha as minhas credenciais de rede (???) e parece que isso que causava o erro, depois disso, tudo funcionou bem. Isso está meio marretado, sugiro pesquisar mais sobre esse problema e se alguém tiver uma solução melhor, faça um comentário, por favor, pois não vou me aprofundar muito nisso...
2º) Ambientes mais recentes (VS 2008/2010 com .Net Framework 3.5 e 4.0)
O projeto de exemplo está funcionando perfeitamente, tentem observar todos os aspectos de configuração da aplicação, não só as classes que consomem os serviços. Repare nos atributos presentes no "app.config" em especial para problemas de acesso, não esquecer de definir o "clientCredentialType" como "Certificate".