Parece que o pacote deb mudou os scripts de integração do shell.
Eles estão localizados em /usr/share/powerline/bindings/
.
Adicione isto ao seu .bashrc no seu diretório pessoal:
# Powerline
powerline-daemon -q
POWERLINE_BASH_CONTINUATION=1
POWERLINE_BASH_SELECT=1
source /usr/share/powerline/bindings/bash/powerline.sh