Quoted from TigerLaw:New Coke was legit at the time it came out...Coke kept losing blind tasting tests to Pepsi which had more sugar, New Coke was designed to be sweeter than Pepsi.
There are a lot of articles on this, here is one I didn't read all the way through but seemed pretty good. http://www.snopes.com/cokelore/newcoke.asp
The problem is the taste tests themselves.
Taste tests are done with a small sip of the drink. Pepsi excels at this because it is sweeter. Over the course of a can though some will find that pepsi is too sweet. This is part of why many people will prefer coke to pepsi. No one takes one tiny sip of a drink.