Parece que nenhuma localidade é gerada. Você selecionou pl_PL.UTF-8 corretamente em dpkg-reconfigure locales pressionando espaço na linha correspondente?
Se sim, a linha
pl_PL.UTF-8 UTF-8
em /etc/locale.gen não é comentado (= não começa com # ). Se você precisar corrigir isso, também precisará executar locale-gen para gerar as localidades. Sua saída deve ser:
Generating locales (this might take a while)...
pl_PL.UTF-8... done
Generation complete.
Se ele não gerar as localidades que você deseja gerar, parece haver algo errado com seu sistema. Um motivo pode ser que você tenha localepurge instalado. Se não houver arquivos em /usr/share/locale/pl/LC_MESSAGES ou /usr/share/locale/pl_PL/LC_MESSAGES , este é o caso ou seu sistema está quebrado.