Some people have reported problems with Relevanssi and non-English characters, mostly accented letters. The problem here isn't with Relevanssi, which handles UTF-8 without problems. The issue lies with MySQL.
If you're having troubles, try switching the collation on the 'term' field in the relevanssi main table (typically wp_relevanssi) to utf8_general_ci (or some other utf8 collation that suits you better). Reindex, and things should work better.
