Да, уже все обновил. Только не по этой инструкции. Удалил все, что ставил через apt-get и скачал с официального сайта бинарники. Там помимо самой ноды и npm идет. Закинул симлинки в /usr/bin/ и /usr/sbin/ и все заработало. И express установился, и даже проект создался и запустился.
Ты в качестве шаблонизатора так же Jade используешь, или что-то другое?