I had a great experience at work, where networkx was too slow to work on the graph that I was working on, and igraph handled it perfectly, quickly, in python, and with just as simple an API.

Worth the pain to get it installed (IIRC, was a while ago, may have changed, etc.)

They now have a PPA Debian/Ubuntu archive for igraph and python-igraph:

  http://launchpad.net/~igraph/+archive/ppa

igraph is also a must-have for network analysis in R. Great for data analysts familiar with the environment.