You need to add the resteasy-hibernatevalidator-provider to your WEB-INF/lib directory. That's what glues togheter resteasy and hibernate validator.
Thanks Andrei for the anwser,
though I'm deploying an .ear and not a .war should it be placed under the lib folder of the .ear ?
Mathieu, the idea is that resteasy finds the provider in your application's classpath... so yeah, put it in the lib of the .ear and it should work fine.