I'm not quite sure I understand your gripe properly. You're saying that since C++ has classes, and classes are defined in header files, that calling code is dependent on the class because... it's in a header file?
If it bothers you so much, use the PIMPL idiom. Or forward declarations where you can. Or template your calling code and write to static interfaces. You've got plenty of options, you just need to know how to use them. C++ is admittedly a very large (arguably too large) language, which is both it's most compelling feature and it's biggest drawback. You can use it for pretty much everything, but fully grasping the language and knowing when to use what feature takes time. This is partly due to trying to maintain backward compatibility with C, while still incorporating new language features. Because of this hodgepodge, iterative development, some dubious choices have been made. D is meant to take the good parts of C++ and cut out the bad; it is a good idea, and a lot of the foremost C++ experts are D supporters. It's a shame that D will probably never take off.
If you're going to complain about C++, at least use valid complaints. Like about how 2 primary aspects of the language (templates and OOP/dynamic polymorphism) are partly incompatible, or about how there's no dynamic multi-dispatch built in to the language still, or how there's no concepts, or how C++11 async doesn't really give task parallelism. (And yes, there are others, many others). But classes and header files? Cmon.
And yes, the famous, fictional interview...