So clearly I agree that adding primitives is an extremely important ability. But it's already nearly if not completely there in all the OO languages I use, using classes.
I don't think primitives are enough, though. The interface / implementations of interfaces combination is also essential to my programming. Being able to say "Curve" and have it mean Straight or NURBS curve or Circle or Offset curve or Composite curve or... is another huge simplifying device. In fact, I've just looked at my code, and I have 15 distinct curve types, at least 5 of which I'd have missed if you asked me to list them, despite having written all of them over the years. That is exactly the power of simplifying abstraction.
Let me point out that given a sufficiently capable OO language, this doesn't need inheritance to implement. This is just the implementation of a role or interface. But it does need classes.
That aside, you're quite right that when one has a common construct that permeates the entire program, one badly wants to give it first-class status in the language. What I've noticed, though, is that these constructs don't tend to get involved in complex object graphs (or if they do, they're leaf nodes). Rather, they tend to be atomic and universal (i.e. interoperable with anything) and simple. So I wonder if what one really wants here is the ability to add new primitives to the language. That's potentially quite different from classical classes. It's more related to the "build up a language that fits the problem, then code the solution in that language" idea.