We have exactly the same problem with import/export to XML in Glossary module. I recompiled my php with mbstring enabled and set up str* function overriding feature in php.ini (mbstring.func_overload=2). Unfortunately it did not work so far.
The problem with grouping was not connected to mbstring features directly, as you can see from the code, it is a hard coded one byte grouping. Another problem was to change the comparison code, which uses strtoupper(). As I mentioned, mb_* version of the function did not helped. Thats why I removed strtoupper() functions for non ASCII characters in my patch and it works fine (at least for Georgian language). BTW the version I am using is 1.4.4 (2004083140)
I will definitely post solution if Ill have.