To use non-ascii characters, you need prefix the string literal with a
'u'.  For example:
I thought that the u"string" notation was only needed when characters had to be handled with their utf-8 code

Replacing the r's with u's in the strings in your example solves the
problem for me on 0.91.2.  (I wasn't able to test 0.90.1 -- that still
may have internal problems handling Unicode strings in some backends.)

This works fine for me with the SVN version (matplotlib :  0.98pre) but not with matplotlib 0.90.1