If you cannot fulfill a request, it is imperative to return an appropriate status code. Since the client is at fault and can correct the state, the 4xx-class of codes seems fitting. From RFC 7231, section 6.5:
The 4xx (Client Error) class of status code indicates that the client seems to have erred.
The way I see it, there are three applicable codes:
400 is a bit broad in definition and has been turned (at least that is my impression) into a catch-all status. So if you are unsure, 400 is almost always a safe bet.
This status is often linked to the HTTP authentication framework. Unjustly so. From the RFC:
The 403 (Forbidden) status code indicates that the server understood the request but refuses to authorize it.
[...] a request might be forbidden for reasons unrelated to the credentials.
In this scenario this would be a bit of a stretch, but not entirely unreasonable.
The 409 (Conflict) status code indicates that the request could not be completed due to a conflict with the current state of the target resource. This code is used in situations where the user might be able to resolve the conflict and resubmit the request.
IMHO this is the one to pick. The RFC is mentioning the PUT
verb but avoids strictly linking 409 with it.