The effect of air pressure on the melting point
For most substances, higher pressure (or air pressure, in your case) will cause the melting temperature to go up. To think about it intuitively, imagine that you have a certain solid. Melting it would increase the volume of that substance because liquids take more space than solids. If you increase the pressure, it becomes harder for that transformation to occur. It's harder to change into a state that needs more volume if you are under pressure! So, you need more energy, hence temperature, to melt.

Notice that this relation is actually reverse in water. Because ice takes more volume than liquid water, it's actually easier to melt it at high pressure and it requires less heat. Try taking an ice cube and apply pressure on it with a knife, see how it liquifies at the contact point.