How/Whether to correct a wrong paper published in a prestigious journal
It is hard to tell whether you are on firm or shaky ground. If the ground is firm, probably the best way to approach it is to write a paper yourselves with correct results and see if the same journal will publish it. 

But, the ground may be shaky for the following reasons. 

In mathematics, a failed proof doesn't leave the result false, just unproven. It gives no evidence for the validity of the claim. A counterexample, on the other hand, leaves the result certainly false. So, it may be that, while an argument fails to deliver, the overall result is still correct, just not provably so. 

But a result that is (if true) contradictory to the original, then the original must be false. This is actually stronger than a counterexample, since a counterexample only shows that a general statement is false, but might leave some specialization of it true, provided that the specialization excludes the counterexample. 

However, in this case you say that your analysis leads to different results. If those results are contradictory to the original claims, and if your reasoning is correct, then you may have the basis of a paper. 

However (again), if your results aren't, in fact, contradictory, then your advisor is giving good advice that you explore the intersection of what it is that the original paper claims and what you claim from your analysis. This might also give you the basis for a good paper, leaving some of the original claims win place, but improving on them. 

I suspect that the situation is complex enough that a simple letter to the editor of the journal, pointing out the error, isn't going to be sufficiently compelling for anyone to take action. If the journal in which you find the original is reputable, then many people have missed the errors, implying a certain subtlety. This leads me to suggest that a full paper laying out the situation is more appropriate. 

And even if this invalidates some early work of your advisor, he is at an advantage in being part of the process that corrects it.