O problema

Você está lá felizão, criando seu programa em Python, decide usar a biblioteca "locale", faz o import e o setlocale conforme código a seguir:

import locale

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

E ao executar o script recebe o seguinte erro:

locale.Error: unsupported locale setting

O problema ocorre porque você não possui a locale desejada em seu sistema operacional.

A solução

Para resolver o problema em distribuições baseadas em Debian e Ubuntu é simples, abra um terminal e digite:

sudo dpkg-reconfigure locales

Marque o locale desejado, neste caso pt_BR.UTF-8 e confirme.

Aos usuários de outras distros, pesquisem sobre como gerar locales no sistema.