I notice from your SO post that you do not have a web.xml. I don't know what app server you are using and how it is supposed to be configured, but our tutorial app explicitly declares a servlet mapping for JAX-RS.
Hope that helps.
Is there more configuration needed? I've added Web.xml file from errai tutorial.