Alinks do not work for cyrillic alphabet. At least.

After failing to get the module work for my Cyrillic alphabet based site, I just gave a shot for a word written with Latin alphabet and, bingo, it worked. Then I supposed that encoding setting in DB was incorrect, went there and found out that actually it's been set correctly - to utf8_general_ci. So where could be the problem? Or this module initially was made only for using with Latin alphabet languages?