I'm a fan of making FGL more record-based, but definitely keeping the inductive graph style.
My own biggest gripe with previous versions of FGL was that the graph implementations were severely underoptimized. In particular, PatriciaTree left open a lot of optimization.
Ivan, would you like to set up a darcs repo for FGL-Prime or something at
code.haskell.org, and start cracking? I'm really excited for this project.