I could really see him as fire, though. If you think, three gurus, three magic types. Belthasar could be water, and Gaspar could be Sky or Light or whatever you'd like to call it.
Reasoning:
Melchior gets trapped in ice on Mt. Woe, which may mean he's not able to defend himself against it as well. Also, he forges weapons, and you need a lot of heat to do that, but I saw no anvil or hammer or anything to indicate he could make a weapon without magic.
Belthasar just seems so knowledgable about the icy Death Peak.
Gaspar lives on a platform that floats to nowhere from nowhere in the middle of the air at the end of time. With a light. It's a shaky connection at best.
Edit: Also, I'll point out Belthasar's writing "All life begins and ends with Nu" and the fact that the localized names are those of the three kings of the nativity story. In most religions, all life begins and ends with water. Another shaky Belthasar to water connection.