Two things:

(1) Speedup.  I haven't been helping much here;  apologies.  Christian 
suggested that a C implementation of gcd might help.  Is this true, or 
are we not yet at the stage where the gcd calls are significant?  There 
are some basic tricks that can speed up the usual Euclidean algorithm by 
a constant factor, and I'll try to implement them if that's of interest 
(unless Christian beats me to it). There also some serious super-fast 
recursive gcd algorithms, with running time O(n**(1+epsilon)) for a pair 
of n-bit integers, but those are complicated and probably best left to 
GMP.

(2) PEP 3101:  Should Fraction get a __format__ method?  I'm looking at 
implementing Decimal.__format__, and I think there's quite likely to be 
a fair amount of common code (e.g. for parsing the format specifier) 
between Decimal.__format__ and Fraction.__format__, so it would probably 
make sense for me to do both of these at once.