Como @geon observou em StackOverflow :
Eu usei o apt-get para instalar o nó. O NPM não foi incluído nesse pacote, por isso teve que ser instalado separadamente. Eu supus que isso funcionaria, mas aparentemente a versão npm na distribuição do Ubuntu estava desatualizada.
O nó wiki tem esta instrução:
Obter uma versão recente do Node ou instalar no Ubuntu antigo e outras distribuições baseadas no apt podem requerer algumas etapas extras. Exemplo de instalação:
sudo apt-get update
sudo apt-get install -y python-software-properties python g++ make
sudo add-apt-repository ppa:chris-lea/node.js
sudo apt-get update
sudo apt-get install nodejs
Depois disso, o npm já estava incluído e funcionou perfeitamente.