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 characters without problems (if you’re not using Unicode, but some other character set, you may indeed be out of luck).
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). Re-index, and things should work better.