if your private methods are complicated enough that you're not able to achieve sufficient coverage through public interfaces it's time to refactor. make the private code a library that you can test in isolation.
When I did C++ programming, I would test via public interfaces. If it didn't seem sufficient, or got messy, the reason would always be "This is a big class that is doing a lot of stuff." I would then identify all the things the class was doing, make classes for each one, and have instances of them in the original class as private members.
This way I could test the individual classes easily, and still test the (formerly) big class using only the public interface (with appropriate mocking as needed).
The main thing I learned from unit testing is to pay little attention to the word unit. Insisting on testing the private methods after the exercise above is usually a symptom of aiming for a level of intellectual purity that does not benefit the code.
(Of course, a better solution may be not to use OO to begin with, but that's a whole other discussion).
