It's certainly possible to foul up a plug in cruise by running too rich. I've never had it happen, but it could. As a previous poster said, I would guess that a carbed engine would be more susceptible, as they are a little more likely to have one or more rich cylinders. Some aircraft (such as the 172R) actually recommend leaning even in the climb, above 3000' to get peak RPM.
As far as the cold starting, I have found that the best way to start a 172R engine cold is to prime the crap out of it. I suspect there are 2 things at work. First, the cold air is denser. Second, in the colder air the fuel will not vaporize and ignite as easily. I did have one occurrence in a carbed 172 where after trying a cold start we couldn't get the thing to light off for the life of us. My CFI siad something about frosting the spark plugs. That's all I've ever heard this phenomenom, and I'm kind of curious about whether or not its an OWT.
Also, point of order to the OP-EFI stands for electronic fuel injection. All mainstream aviation fuel injection systems are hydro-mechanical.