Computer programming is young enough as a field that the mainstream hasn't realized it isn't possible to fit everything into one unified taxonomy. (Biologists and librarians have both spent over a century trying, and they have a lot of insight on the matter.) Putting types into a hierarchy is a useful abstraction sometimes, but there's not some Grand Truth in it -- often, attempts at cramming disparate elements into a hierarchy just create extra complexity. Most systems will keep trying to turn back into graphs unless you anchor the hierarchy in a specific context (what does 'a IS-A b' mean, really?), and the context tends to shift with the problem definition.

Worse still, it's the sort of complexity that looks like work, even though it's usually more like flailing in quicksand.

I think not having to deal with class hierarchies is a big reason why some people find dynamically-typed languages so freeing. I'm still kind of new to Erlang, but I think its push towards modeling things via a graph of communicating processes, with a relatively flat type structure, is worth considering as an alternative. It explicitly focuses on the message protocol between actors, rather than a tree of subtypes. Granted, I haven't worked a large enough project to see it break down and get ugly yet. (C++ style OO sounds good on paper, too.)

Regardless, it isn't classes per se that lead to OO's problems, but the tendency to overuse inheritance. Among statically-typed languages, Haskell's typeclasses seem like another good solution - they break the hierarchy of inheritance up into composition of properties.

Also, the late-binding in OOP means that any class can potentially be responsible for maintaining its invariants even after any of its methods has been overridden by any possible future subclasses. That's not necessarily true even with dynamically-typed languages.