Question: Everything is in the title: Why does it take time to melt ice when the loss of magnetization of a material at its Curie temperature is immediate?
Have you an explanation for this difference?

Answer: 
The melting of ice is a *first order* phase transition. 

First order phase transition involve the release/absorption of a fixed amount of [latent heat](https://en.wikipedia.org/wiki/Latent_heat) per unit volume. A finite amount of time is needed for the release/absorption of such heat, and thus for completing the transition.

The loss of magnetization of a ferromagnet at the Curie temperature is a *second order* phase transition, where there is no latent heat involved.
In addition to Valerio answer, while liquid water has a higher energy level than ice (which you need to provide for the phase transition. Magnets, on the contrary store some potential energy (You can observe it if you break a magnet parallel with the field lines, parts will turn to make a shorter magnetic circuit, and even more if you reduce it to dust. And so, passing the Currie point will free some energy instead of absorbing it, which can happen instantaneously.