No Ubuntu, você deve o apt (Advanced Package Manager) para instalar bibliotecas relacionadas sem quebrar o sistema, já que o pip pode não saber exatamente onde deve procurar por dependências, bibliotecas e tal. Simplesmente correndo:
sudo apt-get install python-nose
deve ser o suficiente. Você também pode verificar a seção de bibliotecas no Ubuntu Software Center para mais ... bibliotecas. Se você não tem certeza se o Ubuntu inclui a biblioteca, você pode pesquisar a lista de pacotes aqui: link