Good change.

My knowledge of Russian isn't native speaker level, but doesn't "не верно" simply mean "not valid"? It seems like the previous translation "уже существует" is more descriptive. Does "не верно" infer that it doesn't exist?

exist validation rule means that record must exist in given database table. So, when validation fails this means that record does not exist, i. e. specified attribute is invalid, and "already exist" message is absolutely wrong (since this value does not exist at all).
"Already exist" message is more related to unique validation rule (and you can see that messages for both rules are eqivalent in the Russian translation, but not in English one, which is probably copy-paste issue).

Oh, my bad! I got my validation rules mixed up.