Problemas com conexão 3G

Tenho uma app que faz uso de um xml consumido através de um webservice http. Quando está ligada no wifi funciona numa boa, mas no 3g ta dando erro Http Status 404.

Isso acontece tanto no smartphone quanto no pc. Acho muito estranho o fato do erro ser Http Status 404 e não de time out ou coisa parecida.

Algumas informações importantes:

1 - A url do webservice muda algumas vezes durante o dia, então eu atualizo sempre antes de fazer a requisição. Pode ser cache da rede 3G? Já tentei limpar de tudo qto é jeito mas o erro continua;
2 - Testei tanto na app android quanto em uma aplicação client de testes que eu desenvolvi, sempre que está no 3G da pau.
3 - Por que erro 404? Tá meio sem lógica, não conheço bem a aplicação do host (é desenvolvida por uma equipe de fora do país), mas será que a cada mudança de url eles matam a referencia à anterior do servidor? Talvez isso justifique o erro.

Segue o fonte:

view plaincopy to clipboardprint?
HttpParams httpParams = new BasicHttpParams();  
        HttpConnectionParams.setConnectionTimeout(httpParams, 10000);  
        HttpConnectionParams.setSoTimeout(httpParams, 10000);         
          
        System.setProperty("http.keepAlive", "false");  
       HttpClient client = new DefaultHttpClient(httpParams);  
       HttpGet get = new HttpGet(url);  
             
      get.addHeader("Referer", "http://rast.sample.com/sample/");  
      get.addHeader("User-Agent","Mozilla/5.0 (Windows NT 6.2; WOW64) AppleWebKit/537.22 (KHTML, like Gecko) Chrome/25.0.1364.97 Safari/537.22");  
      get.addHeader("Content-Type","application/x-www-form-urlencoded");  
      get.addHeader("X-Requested-With","XMLHttpRequest11");  
      get.addHeader("Accept","application/xml, text/xml, */*");  
      get.addHeader("Cache-Control","no-cache"); // HTTP/1.1  
      get.addHeader("Expires", "Sat, 26 Jul 1997 05:00:00 GMT");  
      get.addHeader("Connection","close");  
             
         
     HttpResponse resp = client.execute(get);  
     HttpEntity entityResp = resp.getEntity();  

Debuga em algum aparelho android usando o 3g, e tenta ver o log… Deve ser o timeout.

Já fiz isso, inclusive já coloquei timeout de 1min. Nada resolveu.

Tentei capturar o tráfego com HttpAnalyzer, mas ele enxerga o que trafega entre o pc e o celular (que no caso é o modem). Existe um sniffer para android?