404 Not Found or Bad Request?

404 may cause a confusion - is the resource missing or is the actual URL incorrect?

I'd personally go for the 422 code:

   The 422 (Unprocessable Entity) status code means the server
   understands the content type of the request entity (hence a
   415(Unsupported Media Type) status code is inappropriate), and the
   syntax of the request entity is correct (thus a 400 (Bad Request)
   status code is inappropriate) but was unable to process the contained
   instructions.  For example, this error condition may occur if an XML
   request body contains well-formed (i.e., syntactically correct), but
   semantically erroneous, XML instructions.

404 is your best response. According to the HTTP RFC, http://www.ietf.org/rfc/rfc2616.txt,

A 400 Bad Request means:

The request could not be understood by the server due to malformed syntax.

Whereas, 404 states:

The server has not found anything matching the Request-URI.

The entire URI is your resource identifier, and you're not finding a matching resource for that particular identifier.