I agree with Vincent in that, of the available defined status codes, 400 is the best. The client should know whether or not a category id is valid at the time it submits the request, and is therefore providing bad request content to the server.
With regard to some of the other answers provided:
404 Not Found - This is not the correct status to use, since the resource you're sending the request to actually was found - it was just a referenced resource within the provided resource that was not found.
406 Not Acceptable - This status is, like Evert commented, used with the Accept headers; see section 10.4.7 of RFC2616:
The resource identified by the request is only capable of generating
response entities which have content characteristics not acceptable
according to the accept headers sent in the request.
409 Conflict - This status is intended for conflicting states of resources, typically due to modifications to the resource perhaps by another channel or thread. The RFC (section 10.4.10) gives an example:
...if versioning were being used and the entity being PUT
included changes to a resource which conflict with those made by an
earlier (third-party) request, the server might use the 409 response
to indicate that it can't complete the request
HTTP does provide an alternative to 400 - if fitting, you can create your own 4XX status for this situation. In section 6.1.1 of the RFC:
HTTP status codes are extensible. HTTP applications are not required to understand the meaning of all registered status codes, though such understanding is obviously desirable.
You could therefore define your own custom "430 - Referenced Resource Not Found" or something similar. HTTP-abiding clients should, if this status is unknown to them, treat it as a 400, but if clients are being coded specifically to the API, they should be able to handle it as a 430 and work with it appropriately.