Well one explanation if it is the starter would be when it is colder the battery is weaker, and if the starter armeture is damaged it takes more power to move it past the damaged point, with the decreased power form the battery when its cold this is a possibility.