If I had to do it over again I would have used OverflowError only for some very narrowly defined conditions and ValueError for "logical" range limitations. In particular OverflowError suggests that the abstraction is slightly broken (since we usually don't think much about how large an integer fits in a register) while ValueError suggests that the caller passed something of the right type but with an inappropriate value.

I'm not too worried about breaking APIs in this case (but that could change if someone finds data showing there are common idioms in actual use that would break).