Newton's Law of Cooling
Basically what it says is that the farther the object's temperature is from the ambient tempeture, the exponentially faster it approaches the ambient temperature. So as an object gets closer, it slows down.
Thus, if you put the soda can in the freezer it has farther to go and thus cools faster.