Demorou um pouco para descobrir que o symlink para a paleta de cores do newt apps foi alterado:
$ ls -l /etc/alternatives/newt-palette
lrwxrwxrwx 1 root root 26 Dec 28 2014 /etc/alternatives/newt-palette -> /etc/newt/palette.ubuntu
Para colocar de volta:
$ sudo ln -sf /etc/newt/palette.original /etc/alternatives/newt-palette