This paper presents experimental values for the coefficient of restitution (en) for millimeter-sized ice particles colliding with massive walls at different temperatures. Three different wall materials are tested: hardened glass, ice and Acrylonitrile butadiene styrene (ABS) polymer. The results show a high sensitivity to impact velocity Vi, where en decreases rapidly with increasing Vi. The results also show a decrease in en with increasing temperature T. A novel model that predicts en based on the assumption of collisional melting and viscous damping caused by an increased premelted liquid-layer, is proposed. The model predicts both the velocity and the temperature trends seen in the experiments. The difference obtained in experiments between wall materials is also captured by the new model. A generalized regime map for ice particle collisions is proposed to combine the new model with previous work.