1. Contrary to what you might have learned from Star Trek and Star Wars, planets do not have a single climate.
So it's not really reasonable to say "Winnipeg is as cold as the surface of Mars", unless you're going to specify where on Mars you are talking about. And when in the Martian year you are talking about it. Geekquinox, the blog that first started the current trend of comparing Canada to the Red Planet, was looking at the afternoon temperature (sans wind chill) in Winnipeg on December 31st (-31 degrees Celsius) and daily temperatures collected in November and December by the Curiosity Rover, at Gale Crater, Mars (lowest afternoon high: -31 degrees Celsius). This comparison leaves out the fact that Gale Crater is in the Martian tropics. In the mid-latitudes, however, the average temperature is closer to -50 degrees Celsius. Also, Mars has huge temperature swings from day to night. On the same day that Geekquinox reported a monthly average high at Gale Crater of -31 C (Sol 486) the monthly average low was -110 C.
2. Atmosphere matters
Fun fact: The temperature on the literal surface of Mars — as in, right there in the red dirt — is a lot warmer than the temperature just one meter up. At the CBC Newsblog, John Bowman helpfully pointed this out:
The website of the Curiosity rover weather station says that Mars's "atmosphere is extremely tenuous, about 160 times thinner than Earth's, so heat from the Sun can easily escape. It makes that there are big differences between ground temperature and air temperature. Imagine you were on the Martian equator at noon, you would feel like summer at your feet, but winter in your head " Also, Mars's air is so thin that it doesn't hold onto the heat the way Earth's does.
3. Overlapping temperature ranges overlap
If the the range of all possible temperatures for all possible locations on the surface of Mars is 20 degrees Celsius to -153 degrees Celsius, and the same range for Earth is 56.7 degrees Celsius to -89.2 degrees Celsius, then there is a lot of room for Earth to be hotter than Mars, colder than Mars, or the same temperature as Mars. That one of those conditions occurred should not be terribly surprising. In fact, on the same basis, you could also say that Winnipeg was hotter than Mercury.