Ice does not always melt in water. Liquid water is not necessarily warmer than ice, particularly if you're talking about highly saline water. When salt water freezes, it does so below 0 °C, and the process of freezing mostly desalinates the ice (it's called "brine rejection"). So the mostly freshwater ice sits atop the salt water, and they are both in thermal equilibrium, somewhere between 0 °C and -1.8 °C.
The solid-liquid distinction is completely irrelevant to why ice melts. All that matters is the temperature gradient. For ice to melt it must be in thermal contact with something that is above the melting point of the ice. Fresh liquid water is almost always above this temperature.