From your specification link:
If none of the entity tags matches, or if "*" is given and an existing entity does not exist, the server MUST NOT execute the requested method and MUST return 412 ("Condition with termination condition"). This behavior is most useful when a client wants to prevent a change in an update method, such as PUT, from changing a resource that has been changed since it was last restored.
Since the specification requires HTTP 412 (indeed, it uses "MUST"), and because it is clear that they take into account the particular use case used, HTTP 412 seems to be the correct response code.
412 is still reasonable. The request indicates that the update is conditional. 412 says the condition failed, so the service will not do this. Moreover, 412 is a good correspondence to the concept of conditional queries; 409, it would seem, are tied to a certain type of refusal, which may or may not be conditional in nature. For example, I could see that the service returns 409 in response to an unconditional request for a POST file with an internal conflict.
But see the following, also from the specification:
10.4.10 409 Conflict
The request could not be completed due to a conflict with the current state of the resource. This code is only allowed in situations where it is expected that the user will be able to resolve the conflict and resubmit the request. The response body MUST include enough information for the user to recognize the source of the conflict. Ideally, the response object will contain sufficient information for the user or user agent to resolve the problem; however, this may be impossible and not required.
Conflicts most often occur in response to a PUT request. For example, if version control was used, and the PUT object included changes to a resource that conflicts with those made using an earlier (third-party) request, the server can use a 409 response to indicate that it cannot fulfill the request. In this case, the response object is likely to contain a list of differences between the two versions in the format defined by the Content-Type response.
In any case, the specification seems to require 412 in conditional query conditions, while assuming version conflicts are the key driver for 409s. Perhaps 409 will be used where a version conflict occurs as part of an unconditional request.