Rambam (Mishna Torah, Hil. Edim 18:3) notes that this rule is a g'zeiras hakasuv and gives no reason.
According to Ramban (Devarim 19:18)(as expounded upon by Ralbag and Abarbanel), the logic is as follows: When we have two pairs of witnesses in contradiction (i.e. "Reuven did X" vs. "Reuven did not do X") then we have no reason to believe one pair over another and may not take any form of action. However, here, Pair A of witnesses say "Reuven did X". The fact that they were present at a certain place at a certain time is not technically part of their testimony; it is just necessary background information. Thus, Pair B of witnesses, when they say that Pair A were in fact somewhere else at that time, they render Pair A's testimony impossible, and yet they have nobody technically contradicting them, since to do so there would need to be witnesses that Pair A were indeed at the relevant place at that time. (And Pair A themselves cannot testify concerning themselves.)
Ran in his d'rashos (11) gives another reason: We believe the witnesses who have less ability to lie. The first witnesses can set up a story and create false testimony and perhaps they were confident that nobody saw them elsewhere at the time they specify in their testimony. But if it is Pair B that is indeed lying, how are they not worried to testify falsely when Pair A knows that they are lying? All Pair A would have to do is bring other witnesses that they know were at the scene of the crime as well and saw them there. Thus, it is more likely that Pair A are the false witnesses since they have more "ease" in lying.