If "validation failure" means that there is some client error in the request, then use HTTP 400 (Bad Request). For instance if the URI is supposed to have an ISO-8601 date and you find that it's in the wrong format or refers to February 31st, then you would return an HTTP 400. Ditto if you expect well-formed XML in an entity body and it fails to parse.
Richardson and Ruby's RESTful Web Services contains a very helpful appendix on when to use the various HTTP response codes. They say:
400 (“Bad Request”)
Importance: High.
This is the generic client-side error status, used when no other 4xx error code is appropriate. It’s commonly used when the client submits a representation along with a
PUT or POST request, and the representation is in the right format, but it doesn’t make
any sense. (p. 381)
and:
401 (“Unauthorized”)
Importance: High.
The client tried to operate on a protected resource without providing the proper authentication credentials. It may have provided the wrong credentials, or none at all.
The credentials may be a username and password, an API key, or an authentication
token—whatever the service in question is expecting. It’s common for a client to make
a request for a URI and accept a 401 just so it knows what kind of credentials to send
and in what format. [...]