Did you verify the message that actually goes to the wire, to see if ws-security is actually being used? Did you provide the proper descriptor (http://community.jboss.org/wiki/JBossWS-NativeUserGuide#Client_side_WSSE_declaration_jbosswsseclientxml) for configuring that?
There're many working examples in the sources, take a look at the org.jboss.test.ws.jaxws.samples.wssecurity package for instance.
There's also an "advanced" example described step by step on the wiki on this topic, see http://community.jboss.org/wiki/JBossWS-Securityandattachmentssample