The main difference between warming 'solid' butter and warming solid ice is that one is a mixture and one is a pure substance.
Ice has a crystal structure set in place by the shape and polarity of the water molecule. It requires quite a bit of energy to be removed from 0 degree water to cause the formation of the solid phase. The structure has two options - remain water, or, once cooled enough, become solid.
Butter is a mixture of fat and water and other components. As this mixture warms, the fat component changes viscosity and becomes more liquid and less sludgy. The water does not change much, but is trapped in the layers of the fats. At 40 F, just above refrigerator temperature, butter is 'hard' because the fats are not flowing. As the temperature warms, the fats start to move, thus softening the butter.
The butter softening behavior can be seen in some metals as they get heated close to the melting point. Iron becomes 'soft' and malleable, and can be forged. Ice has a particular, rigid structure, so never has a 'soft solid' stage.