Why doesn't setting the locale fix this UnicodeError?

I have the following Python script:

# -*- coding: utf-8 -*-
import sys, locale
locale.setlocale(locale.LC_ALL, 'en_US.utf8')
print '肥皂' # This works
print u'肥皂'

When running the script I get:

肥皂
Traceback (most recent call last):
  File "../pycli/samples/x.py", line 5, in <module>
    print u'肥皂'
UnicodeEncodeError: 'latin-1' codec can't encode characters in position 0-1: ordinal not in range(256)

However, when I explicitly set the LC_ALL environment variable in the shell then it works

export LC_ALL=en_US.utf8

So I'm wondering why doesn't the setlocale() have the same effect?