I don't know, is it bug related to all not latin character, but I sure it related at last to russian characters.
It works fine for me on Windows 7 x64:
Tested both with UTF8 and Cyrillic 1251 encodings. So the issue might be MacOS specific.
I'm experiencing the same problem on Ubuntu 12.04, ST2 version 2.0.1 build 2217 (trying to search text in Russian).
That's very annoying, I will be happy to provide any debugging information that's necessary...
Still relevant and very annoying... please look into this
Confirm the bug with cyrillic symbols, OS X 10.9.2 (13C64), Sublime 3059.
I confirm this bug on build 3088.
Seems that it finally has been fixed in 3103 (OS X). Thank you very much! :)