Parece que a versão do npm não é mais suportada, o nó de atualização (e npm com ele) resolveu o problema.
Primeiro, desinstale a versão desatualizada (opcional, mas acho que isso corrigiu um problema que eu estava tendo com módulos globais não sendo encaminhados).
sudo apt-get purge nodejs npm
Em seguida, instale a partir do repositório de Chris Lea:
sudo apt-get update
sudo apt-get install -y python-software-properties
sudo add-apt-repository ppa:chris-lea/node.js
sudo apt-get update
sudo apt-get install nodejs