Why does the internal energy increase when ice melts to give water?
Potential energy refers in this case primarily to the energy associated with intermolecular hydrogen bonds between water molecules. The total strength of H-bonds for each water molecule is on average weaker in the liquid. The density is a function of the geometry of the solid or liquid required to accommodate the bonds. Water is odd in that it acquires a spacious bonding arrangement in ice, but this does not mean that bonding is any weaker for that matter. On the contrary, you might say that the geometry is special in order to accommodate those strong intermolecular bonds.
To complement a point made in another answer: the change in internal energy  during a thermodynamic tranformation is the sum of the heat transferred to and work done on the system. Note that work done by a system (here the water) decreases its internal energy. In the case of ice melting under atmospheric pressure, the volume contraction means that the internal energy increases due to work done on the system by the surroundings. This increase in internal energy is on top of the gain due to a transfer of heat from the surroundings.
Note however that the free energy is unchanged during the process (if carried out reversibly), or, equivalently, the joint entropy of system and surroundings is constant. So the transfer of heat to the system (which reduces the entropy of the surroundings) is compensated by an increase in the entropy of water with melting.