Problema com acentuação - Encoding - Java no Linux

Boa noite,

Estou com o problema, é meio complicado de explicar mas vou tentar ser sucinto.

Tenho um sistema web que possui uma função java para retirar acentos de palavras, daquelas básicas que faz replaceAll nos caracteres com acentos e ç.
Esse método funciona bem e não tenho problemas.

Tenho um outro sistema que é um webservice com jaxb e nele tenho um webmethod que recebe uma string como parâmetro, tenho um site (não possui codigo fonte dele) que acessa esse método do webservice e está enviando como parâmetro o valor “Computação” e então para consultar no banco de dados eu preciso tirar os acentos e ç dessa palavra. Na primeira linha do método eu dei um sysout no método e ele imprime certinho a palavra Computação, entretando quando passo a palavra pela função que retira os acentos por replaceAll o sistema está acabando com a palavra e no lugar do ç e do ã fica somente caracteres estranhos. Esse problema não acontece com outros sistemas.

Os 2 sistemas utilizam Jdk 5.0 e estão no mesmo servidor usando linux, o mais intrigante que quando rodo esse webservice pela minha máquina, ou seja local, o problema não acontece, ou seja, somente no servidor linux. Ja tentei de tudo, usando Normalizer, tentei imprimir por sysout uma string os valores áàéè e não imprime nada no servidor linux… Ja pensei que poderia ser alguma configuração da aplicação, do tomcat (que é o 5.0), pois essa merda so acontece nessa aplicação e somente no servidor.
No servidor linux eu imprimi o System.getProperties e saiu que está utilizando o encoding ISO-8859-1, ja tentei fazer um new String() fazendo parse para UTF-8 cp1252 e nada resolveu.

Alguém já passou por algo parecido ?

Agradeço desde já quem puder ajudar.