4.5 isn't the section used to determine the underlying type of a non-explicitly typed enum, it's 7.2 (paragraph 5 in the old standard and paragraph 6 in the new standard). Both versions of the standard contain the wonderfully non-specific line "It is implementation-defined which integral type is used as the underlying type except that the underlying type shall not be larger than int unless the value of an enumerator cannot fit in an int or unsigned int." Note that it says the value of an enumerator not that range of the all enumerators must simultaneously fit within an int or unsigned int.

Well, 4.5§3 states

A prvalue of an unscoped enumeration type whose underlying type is not fixed (7.2) can be converted to a
prvalue of the first of the following types that can represent all the values of the enumeration (i.e., the values
in the range bmin to bmax as described in 7.2): int, unsigned int, long int, unsigned long int, long
long int, or unsigned long long int. If none of the types in that list can represent all the values of
the enumeration, a prvalue of an unscoped enumeration type can be converted to a prvalue of the extended
integer type with lowest integer conversion rank (4.13) greater than the rank of long long in which all the
values of the enumeration can be represented. If there are two such extended types, the signed one is chosen.

which would seem to apply to enums, no?

7.2 §5 states

Each enumeration defines a type that is different from all other types. Each enumeration also has an
underlying type. The underlying type can be explicitly specified using enum-base; if not explicitly specified,
the underlying type of a scoped enumeration type is int. In these cases, the underlying type is said to be
fixed. [...]

but, this isn't a scoped enum (enum class / enum struct), so the type is not fixed and 7.2 §6 states

For an enumeration whose underlying type is not fixed, the underlying type is an integral type that can
represent all the enumerator values defined in the enumeration. [...]

Which would seem to lead to the same result as 4.5 §3

In any case, yes, C++11 is not backwards compatible with C++99. In fact even the auto keyword used to have a different meaning.

For an enumeration whose underlying type is not fixed, the underlying type is an integral type that can
represent all the enumerator values defined in the enumeration. [...]

Which would seem to lead to the same result as 4.5 §3

See also language defects #1618 (Gratuitously-unsigned underlying enum type) and #1636 (Bits required for negative enumerator values).

Enumerations and enumerators on cross-platform code are an implementation-defined mess. They mostly work okay and they generally work as programmers expect, but for their actual inner workings they play fast-and-loose with the rules. Compilers differ on some rather important implementation-defined details. Usually if you stick to a tight family of compilers the functionality is the same, but when you hit broader cross-platform boundaries the behavior becomes difficult. Sharing enumeration-using utility code between PC and Playstation? Not a problem. Sharing enumeration-using utility code between PC, 3DS, and Android? Heaven help you.

C++98 was intentionally vague, leaving almost everything up to the implementation. C++03 they knew about many issues but intentionally didn't address them since it was to be a minor update.

In C++11 the committee notes and discussions indicate that they tried their best to add some specifications and they closed almost all the issues, but they again left much of the inner workings to implementation defined behavior.

See also language defects #1618 (Gratuitously-unsigned underlying enum type) and #1636 (Bits required for negative enumerator values).

Thanks, I'll check those out.