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.