> How about deleting the mapping (pthread_key_delete) and recreating it
> from scratch, then?

Sounds good.
So the idea would be to retrieve the current thread's tstate, destroy the current autoTLSkey, re-create it, and re-associate the current tstate to this new key. I just did a quick test on RHEL4 and it works.
PyThread_ReinitTLS looks like a good candidate for that, but it's the same problem, autoTLSkey scope is limited to pystates.c (and I'm not sure that the tstate should be exposed to platform thread implementations).
There's also PyEval_ReinitThreads in ceval.c, exposing the autoTLSkey would make more sense (and it already knows about tstate, of course).
Where would you put it?