Most recent ruling about this from the Compendium-EX:
== LEGENDARY ASCENT (Articuno EX - EX:Fire Red / Leaf Green; Moltres EX - EX:Fire Red / Leaf Green; Zapdos EX - EX:Fire Red / Leaf Green)
Q. Does Muk's "Toxic Gas" prevent the "Legendary Ascent" Poke-POWER found on the legendary birds of FireRed/LeafGreen from happening? A. No, "coming into play" powers like "Legendary Ascent" are not prevented by "Toxic Gas". (Sep 9, 2004 PUI Rules Team)