O problema é que não há pacote python-igraph
para 12.04. Por causa disso, você obtém o erro quando tenta instalá-lo no 12.04. Você pode verificar o PPA para você mesmo.
No entanto, ele tem um pacote para o 11.10. Se você está desesperado, você pode baixar o pacote deb destinado a 11.10 e instalá-lo manualmente. Espero que você possa instalá-lo sem muito problema de dependência.