Yes, the problem lies in the fact that the representations of many of the Cyrillic letters are more than one byte in length, and the Guile functions which deal with characters don't appear to accommodate these.
I've come up with a solution to the problem, I think. (I hope!)
The variable "all-characters" stores every character which can appear in the lyric text. For testing, I included only those characters which are used in the Russian test of the "Twinkle, twinkle" example. To work with your chant examples, you will need to extend this list to include all Cyrillic letters, uppercase and lowercase, and any punctuation, numbers, etc. you will need. This list must include the symbols which will be colored red, too. It can't include any duplicates, and if something is missing it will also be missing in the transformed text. I realize this is tedious, but I couldn't think of a better way to "teach" LilyPond the new characters.
The variable "characters-to-color" of course includes your list.
Basically, I scan each unit of text to create a list of position/length data, and use this to break the text into its component strings. Then I convert these to markups with some characters in red, others in black. (Of course, you could do other transformations to either of these.)
Let me know if this works as you would like! If you find any problems, let me know and I'll try to fix them.
If anyone reading this thread knows of a more streamlined approach, please let me know.