That's an interesting idea.  I wouldn't make the clients mine, though.  Not everyone has access to a reasonable mining rig.  Just have the clients pay BTC for premium bandwidth.  For instance, offer to pay 0.001BTC per MB of transit.  That's highly profitable for the relays - it's a 100x markup over premium internet transit.  And it'd be a reasonable price for many users who want to go fast.

The two problems I see: 1, you'd have to prepay for your bandwidth, though that's not so bad when you can do very small microtransactions with BTC;  2, if you get your BTC from a non-anonymous source it defeats the purpose of TOR.  Clients who care could mine their own; most won't care since they're not worried about a threat strong enough to trace the coins back.