> It would be nicer if the OverflowError from _PyLong_NumBits 
> were propagated, so that the second case raises OverflowError
> instead of giving an incorrect result

Why not, but I prefer your second proposition: return a long integer. 
Attached patch implements this solution.

>>> x=1<<(2**31-1)
>>> n=x.numbits(); n, n.numbits()
(2147483648L, 32L)
>>> x<<=(2**31-1)
>>> n=x.numbits(); n, n.numbits()
(4294967295L, 32L)
>>> x<<=1
>>> n=x.numbits(); n, n.numbits()
(4294967296L, 33L) # yeah!

With my patch, there are two functions:
 - _PyLong_NumBits(long)->size_t: may overflow
 - long_numbits(long)->long: don't raise overflow error, but may raise 
other errors like memory error