I confirm the bug on 2.7.

$ ./python 
Python 2.7.3+ (2.7:ab9d6c4907e7+, Apr 25 2012, 20:02:36) 
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import locale
>>> locale.setlocale(locale.LC_NUMERIC, 'uk_UA.UTF-8')
'uk_UA.UTF-8'
>>> u'{:n}'.format(10000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
UnicodeDecodeError: 'ascii' codec can't decode byte 0xc2 in position 2: ordinal not in range(128)
>>> '{:n}'.format(10000)
'10\xc2\xa0000'