I've found that dependency injection is the design pattern that most helps make my code testable (and, often, also reusable and adaptable to contexts that are different from the original one that I had designed it for). My Java-using colleagues adore Guice; I mostly program in Python, so I generally do my dependency injection "manually", since duck typing makes it easy; but it's the right fundamental DP for either static or dynamic languages (don't let me get started on "monkey patching"... let's just say it's not my favorite;-).
Once your class is ready to accept its dependencies "from the outside", instead of having them hard-coded, you can of course use fake or mock versions of the dependencies to make testing easier and faster to run -- but this also opens up other possibilities. For example, if the state of the class as currently designed is complex and hard to set up, consider the State design pattern: you can refactor the design so that the state lives in a separate dependency (which you can set up and inject as desired) and the class itself is mostly responsible for behavior (updating the state).
Of course, by refactoring in this way, you'll be introducing more and more interfaces (abstract classes, if you're using C++) -- but that's perfectly all right: it's a excellent principle to "program to an interface, not an implementation".
So, to address your question directly, you're right: the difficulty in testing is definitely the design equivalent of what extreme programming calls a "code smell". On the plus side, though, there's a pretty clear path to refactor this problem away -- you don't have to have a perfect design to start with (fortunately!-), but can enhance it as you go. I'd recommend the book Refactoring to Patterns as good guidance to this purpose.