Web services não acha classe externa

Olá a todos.
Eu desenvolvi um web service pra realizar algumas tarefas. Funciona normalmente. Só que agora eu quero que essas tarefas estejam em uma aplicação externa ao web service (em um outro jar). Estou usando o Tomcat com o Axis para fazer o deploy.
O problema é que na hora que o web service vai chamar a aplicação, dá o erro NoClassDefFoundError. Eu já coloquei o jar no CLASSPATH, no Axis/WEB-INF/lib e no Tomcat/commom/lib e em nenhum dos casos funcionou.

Alguém tem alguma idéia?

Fernando.