I had the same problem, when trying to use a "pt_BR.utf-8" locale and variations, like this:

import locale
locale.setlocale(locale.LC_ALL, 'pt_BR.UTF-8')

So i tried this:

import locale
locale.setlocale(locale.LC_ALL, "Portuguese_Brazil.1252")

Here have a list of variations for most locales