The water thing for Palkia makes a poetic sense. See, a lot of ancient creation myths describe the fabric of the universe, the chaos from which order was formed, as "waters."
And I guess time is made of metal.
Palkia's head is the same type of the fishs, and your "wings" resembles a fin.
Mine's better.
[sarcasm]Make Gyrados water/ice so it can be even better[/sarcasm]
[insert a single frame of me slapping you for being an ass.]
I'd say the reason that Gyarados is water/flying, despite the fact that it's clearly a dragon, is that it's Gen 1, and there was only one dragon family back then. Water/flying is the closest they could get.