I've had a lot of luck with Gephi for fairly complex graphs (~10000 nodes and edges), in particular it has some very powerful layout algorithms. It can be very helpful to have immediate visual feedback when untangling something like that. Nice to see that development is ongoing, the GUI used to feel a bit clunky but 0.10 seems a lot better!