How to proceed when a mathematical result contradicts existing literature?

Certainly the fact that there is a contradiction with previous literature must be prominently advertised; to do otherwise would be scientific misconduct. I would not be confident in publishing such a paper unless I found the mistake in the other paper, or could give a counterexample showing they are wrong.

After having carefully worked out the other paper and my own paper, and asked any experts with whom I have an established connection, I might contact the authors of the contradicting paper (if they are still active). After their response, or lack thereof, I would consider publishing a preprint and after that submitting to a journal. The journal is the slowest and most uncertain way of finding out where the problem is.

Forgetting the issue of publication, when two mathematicians find contradictory results, I think they have the collective intellectual duty to try to figure out what is going on. Generally this should mean that one of the purported proofs is wrong; however, it could also be that an even earlier result (used by one or the other contradictory proofs) was incorrect; conceivably, it could even mean that a contradiction has been found in whatever foundations of mathematics were being used, but we probably shouldn't take this possibility too seriously.

Generally speaking, I would say the burden of figuring out the root of the problem lies with the author of the most recent result (were it only because the others of the other result might be retired or dead). So you can't just go ahead and say "I proved not-X" when X appears in the literature, you need to analyse why and where the proof of X is wrong.

There are exceptions, however. One extreme example would be that if you can find a numerical counterexample to Fermat's Last Theorem (that anybody can check with a computer), you don't need to explain where Wiles's proof was wrong (or even understand it). More generally, if your proof of not-X is conceptually much simpler and/or much shorter than the proof of X found in the literature, I would say that this is a valid reason to shift the burden of finding an error to the authors of the latter.

One valid reason (at least, valid from the point of view of intellectual honesty: it might be another matter to actually convince anyone) not to analyse the proof of X for error is if you don't understand the techniques used therein. If they are too complicated, this might fall under the "your proof is much more simple" category mentioned above. But a genuinely problematic situation might arise if two mathematicians from completely different domains were to prove contradictory results, neither being able to understand the intricacies of the other's proof; third parties would then need to get involved to resolve the contradiction.

But in any case, any contradictory result you are aware of should be explicitly mentioned in a publication, and whatever reason you have not to analyse their proof in search of the error should be explained.

Let me just note that Voevodsky (2002 Fields Medal) describes such a situation that he experienced himself (http://www.math.ias.edu/~vladimir/Site3/Univalent_Foundations_files/2014_IAS.pdf):

In October, 1998, Carlos Simpson submitted to the arXiv preprint server a paper called “Homotopy types of strict 3-groupoids”. It claimed to provide an argument that implied that the main result of the “∞-groupoids” paper, which M. Kapranov and I had published in 1989, can not be true. However, Kapranov and I had considered a similar critique ourselves and had convinced each other that it did not apply. I was sure that we were right until the Fall of 2013 (!!). I can see two factors that contributed to this outrageous situation:

• Simpson claimed to have constructed a counterexample, but he was not able to show where in our paper the mistake was. Because of this, it was not clear whether we made a mistake somewhere in our paper or he made a mistake somewhere in his counterexample.
• Mathematical research currently relies on a complex system of mutual trust based on reputations. By the time Simpson’s paper appeared, both Kapranov and I had strong reputations. Simpson’s paper created doubts in our result, which led to it being unused by other researchers, but no one came forward and challenged us on it.

EDIT (01/01/2018): Let me add another (IMHO, relevant and interesting) example. Asher Peres wrote (https://arxiv.org/abs/quant-ph/0205076):

" Early in 1981, the editor of Foundations of Physics asked me to be a referee for a manuscript by Nick Herbert, with title “FLASH —A superluminal communicator based upon a new kind of measurement.” It was obvious to me that the paper could not be correct, because it violated the special theory of relativity. However I was sure this was also obvious to the author. Anyway, nothing in the argument had any relation to relativity, so that the error had to be elsewhere...

I recommended to the editor of Foundations of Physics that this paper be published [5]. I wrote that it was obviously wrong, but I expected that it would elicit considerable interest and that finding the error would lead to significant progress in our understanding of physics. Soon afterwards, Wootters and Zurek [1] and Dieks [2] published, almost simultaneously, their versions of the no-cloning theorem...

There was another referee, GianCarlo Ghirardi, who recommended to reject Herbert’s paper. His anonymous referee’s report contained an argument which was a special case of the theorem in references [1, 2]. Perhaps Ghirardi thought that his objections were so obvious that they did not deserve to be published in the form of an article (he did publish them the following year [7])."