Why does a Peltier cooler heat up when cooled by ice?
You still have to ensure thermal coupling to the ice. Once your ice melts, it forms a thin layer of water, which is warmer towards your TEC element. Ice by itself is a decent thermal insulator (look at igloos), so the heat from water doesn't have anywhere to go (at least not fast enough). And the layers of water create a gradient with warmest part being on your TEC surface, which eats into your thermal budget. 

Forced air cooling works better despite poorer thermal conductivity of air (as opposed to the water) and higher temperatures than the ice purely because they can ensure that warm air gets blown away.

I think it could be more effective to try using just a water bath as a coolant instead of putting TEC directly on ice. That way heat mixes into the whole bath gradually heating it up. Warmer layers of water next to TEC should "push" their heat away to cooler layers (via convection currents) and this process wouldn't be blocked by the insulating properties of ice. Even better, if you could throw in a ventilator to circulate the water around. If you have access to large amounts of distilled water, you don't have to worry about short circuiting either, not unless water becomes dirty enough to start conducting.