With the caveat that I know absolutely nothing about locales, here's what I've been able to reduce the problem down to:

zinc (alias s11, Solaris 11 x64):
    >>> locale.setlocale(locale.LC_ALL, 'C')
    'C'
    >>> locale.strxfrm('a')
    'a'
    >>> locale.setlocale(locale.LC_ALL, 'en_US.UTF-8')
    'en_US.UTF-8'
    >>> locale.strxfrm('a')
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    ValueError: character U+10105a3 is not in range [U+0000; U+10ffff]
    >>> 

nitrogen (alias s10, Solaris 10 SPARC):

    >>> locale.setlocale(locale.LC_ALL, 'en_US.UTF-8')
    'en_US.UTF-8'
    >>> locale.strxfrm('a')
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    ValueError: character U+101010e is not in range [U+0000; U+10ffff]

Not sure how relevant it is, but on both those Solaris boxes, locale.LC_ALL returns 6, whereas on BSD and OS X it always seems to return 0.