This is something that I've thought about a lot, and you're right when you say that your private method will be tested when you call the public method. My argument against this (watch the Agilists line up to flame me now!) is that testing private methods provides you with a much more granular test that only testing public methods. This is only the case though, if your public methods have complexity to them. If all the public method does is call one private method, then you're essentially testing the same thing. If your public method calls 4 private methods, or even one private method that uses two other private methods, how many tests will you be writing to ensure good coverage of the private methods' functionality? Writing tests for permutations against one function sucks and eventually gets too complicated leading to missed testing scenarios. Testing of the private methods, however you wish to do this, allows you to write much more discrete and readable tests.

Now that I'm done, the Agilists and TDDers can say how I should refactor that public method so it's less complicated and easier to test.

you will find lots of debate on this subject.
The people who are pro of testing private methods said that the benefits that TDD brings to model design on the class level, can be acheived as well on the method level. Beside gives more control, if you refactor later and something brake.
and the people who are opposing that said that TDD is for the class behavior and interaction with the outside world, so how the class is doing inside is irrelevant, beside as you mentioned, all private methods should be called by testing public methods.
Myself, I am not doing unit test for private methods, and just keep it for public