Here's a first try at a patch that converts the Decimal coefficient
from type str to type bytes.  It needs some work:  here are some timings 
for a complete run of the test suite (best of 3 in each case) on my
MacBook.

Python 3.0, str:   12.880s
Python 3.0, bytes: 13.294s
Python 2.6:         9.279s
Python 2.5:         9.212s

There's still some room for speedup with the bytes patch, but at the 
moment it doesn't look as though performance alone is a compelling reason 
to make this change.