アメリカのグリーンカードの当初の正式名称はAlien Registration Receipt Cardで、これだけ長いと省略しようとしますよね、普通。で、初代のカードの色が緑だからグリーンカードが一般的になってみたいですよ。
カナダの場合についてですが、Wikiのフランス語版(
http://fr.wikipedia.org/wiki/Carte_de_r%C3%A9sident_permanent_%28Canada%29)を眺めていてMaple Leaf Cardという名称が一切出て来ない事からの個人的な予想ですが、カナダの場合、国としての公用語が英語とフランス語という事が背景にあるような気もします。
国としてフランス語も平等に扱う事を明言している以上、政府としては「Maple Leaf Card」という英語のみの名称は使えない、という事じゃないかと思います。Permanent Residentなら順序は逆になりますがフランス語でも"Résident Permanent"で綴りも同じ(アクセント記号はありますが)になり平等に扱われている様に見えます。CardはCarteになるのでまったく同じとは言えませんが、少なくとも各単語の頭文字は同じになりますしね。
アメリカの場合はそもそも国としての公用語は制定されて無いですから、事実上の公用語の英語のみで問題は出なかった無かったんじゃないでしょうか。
勝手な推測ですが(笑)