A few issues I'd like to raise:

(1) Multiple callback chains.  Is there any code in your existing use case of GC callbacks where you don't check for the phase argument and follow different code paths depending on it?  If not, having two callback chains should be fine and takes the burden from the programmer to the implementors.  (This is feasible if we *only ever* have two values for the phase.)

(2) Single collections.  Currently, neither PyGC_Collect nor gc.collect() invoke the callbacks (since they do not call collect_generations).  Is this an oversight or intentional?

(3) Error checking.  What about callbacks which are bound to fail on each and every invocation, ie. because of wrong signatures.  Should these be flat-out rejected in some way *on registration*, automagically removed when first encountered, or are we okay with errors slammed into the user's face every so often because he should REALLY fix them?

(4) Interop.  Can this be supported as easily on other VMs?  (That's perhaps a good reason for the statistics to be a dict, for GCs providing vastly different amounts of information.)