Los pares (key,value), los devuelve la función values() de Map. Si llamas a la funcion keySet, te devuelve un Collection algo extraño, depurando en WebSphere salen solo las claves, pero si de ese collection sacas el iterador y lo recorres, te devuelve los pares (key,value) y no solo los key.
En JavaDoc indica que si cambias algo de ese collection, también se cambiará en el Map, por lo que supongo que es necesario que devuelva eso. Es extraño, la verdad.
Lo solucione llamando al toArray() del keySet(), devuelve un objeto:
Object[] = {key,key,key,key,key...}
que me soluciona la papeleta de forma menos elegante, pero al menos funciona!
gracias por la ayuda