It isn't harder to add operations in languages that don't confuse class and object, e.g. if you have a dynamically typed language you could just add whatever operation you needed for a specific object without worrying about hierarchies. The question is whether that just replaces one problem (brittle hierarchies) with another (method-not-supported errors).
I failed to mention that the expression problem, as originally formulated by Wadler[1], is in the context of typed languages. One of the arguments in favor of untyped languages is that they are indeed more flexible that way, but at the expense of type safety. As the science of type systems advances, typed languages are slowly becoming more and more flexible (and, sadly, difficult to learn).
I should have read your original post more closely, hadn't even heard about the Expression Problem. Makes more sense now after a bit of reading - I guess Haskell's notions of static typing are quite different from that of the C family of languages.
