Perhaps you could try what Lookey said. Make it melt in layers. I just sat down for 10 minutes looking at an ice cube melt and it does appear to shrink inwards. To add to the effect, try and put some particle vapour in there to make it look really cold.

If all else fails, you could try a new technique. Have the camera pan towards a freezer door and have the door open to reveal the words "Cool Savings" encrusted in icicles, and ice particles (or whatever that steam in the freezer is called) floating along.

------EDIT-----
Vapour! How could I forget? It's in the 4th sentencee of this post :p