In 2.7, I get:

$ ./python.exe 
Python 2.7a0 (trunk:76501, Nov 24 2009, 14:57:21) 
[GCC 4.0.1 (Apple Inc. build 5465)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import locale
>>> locale.setlocale(locale.LC_NUMERIC, "cs_CZ.UTF-8")
'cs_CZ.UTF-8'
>>> from decimal import Decimal
>>> s = format(Decimal("-1.5"),  ' 019.18n')
>>> s
'-0 000 000 000 001,5'
>>> len(s)
20
>>> s = format(Decimal("-1.5"),  u' 019.18n')                           
>>> s
u'-0 000 000 000 001,5'
>>> len(s)
20
>>> 

Could you give more details on the UnicodeDecodeError you get? Any
traceback?