Some advice explicitly directed at less senior people. I would very much advise some who does not yet have tenure to NOT take the nuclear option (e.g. posting a paper on the arXiv accusing someone of being wrong, or writing irate letters to the editors of a journal). In the extremely rare cases in which this has to be done, it is best done by someone who is both pretty senior and very politically skilled. This leads me to my other piece of advice. Namely, talk to other, more senior people in your research area. First, they might be able to convince you that it isn't really as serious an error as you think. Second, they will probably know the personalities involved better, and be more effective at convincing an author to do the right thing if something has to be done.

The two times something like has happened to me, I had ended up proving stronger results than the erroneous papers by pretty different techniques. I buried remarks at the ends of the introductions of my papers mentioning the wrong papers and explaining where they went wrong. On one of those occasions the author had left math and I didn't know how to contact him, so I didn't correspond with him first (after I posted the paper the arXiv, one of his friends contacted him and we exchanged some friendly emails). The other time, I explicitly cleared the language I used with the original author.