Actually, I think the ends do justify the means. I think the problem comes into play when you don't take into consideration all the ends. The only way we can determine with any reliability what means should be employed are by the ends those means produce.
The ends don't justify the means is merely a misstatement (or simplification) of a situation in which some of the ends are so terrible that the desired ends aren't worth it.
I have always been able to get into some interesting discussions with people when we would start debating, and disagree on some point; and they would ask "Do you think the ends justify the means," which, I'm sure, they thought was rhetorical, because any right-minded person would answer "no," and I would then answer "yes" completely straight faced.
To reiterate, I have yet to have anyone present me with a situation, real or imagined in which I would not base the means on the desired ends.