Well, "newtype pattern" is itself a reinvention of a decades old concept. Presumably "newtype pattern" gets its name from the `newtype` keyword in Haskell, which was introduced in Haskell 1.3 (1996).
To the best of my knowledge, the earliest specific term for the concept is painted types (Simonyi, 1976)[0], but I believe this was a new term for a concept that was already known. Simonyi himself quotes (Hoare, 1970)[1]. Hoare doesn't provide a specific term like painted type for the type being defined, but he describes new types as being built from constintuent types, where a singular constituent type is known as the base type.
Simonyi uses the term underlying type rather than base type. Hoare eludes to painted types by what they contain - though he doesn't explicitly require that the new type has the same representation as it's base type - so they're not necessarily equivalent, though in practice they often are. Simonyi made this explicit, which is what we expect from newtype in Haskell - and specifically why we'd specifically use `newtype` instead of `data` with a single (base) constituent.
If you're aware of any other early references, please share them.
> These examples show that the idea of types is independent of how the objects belonging to the type are represented. All scalar quantities appearing above - column numbers, indices and so forth, could be represented as integers, yet the set of operations defined for them, and therefore their types, are different. We shall denote the assignment of objects to types, independent of their representations, by the term painting. When an object is painted, it acquires a distinguishing mark (or color) without changing its underlying representation. A painted type is a class of values from an underlying type, collectively painted a unique color. Operations on the underlying type are available for use on painted types as the operations are actually performed on the underlying representation; however, some operations may not make sense within the semantics of the painted type or may not be needed. The purpose of painting a type is to symbolize the association of the values belonging to the type with a certain set of operations and the abstract objects represented by them.
> In most cases, a new type is defined in terms of previously defined constituent types; the values of such a new type are data structures, which can be built up from component values of the constituent types, and from which the component values can subsequently be extracted. These component values will belong to the constituent types in terms of which the structured type was defined. If there is only one constituent type, it is known as the base type.
