According to http://en.wikipedia.org/wiki/Pok%C3%A9mon_Stadium, the Petit cup is more restrictive than just level:
Petit Cup: Battle using Basic Pokémon from levels 25 to 30 who fall under a certain height and weight. The most restrictive Cup.
Not only that, but it turns out you can't even use evolved pokemon. Gyrados breaks more than one rule. I think you'll find many of your pokemon aren't selectable for this event.
The rules for the Petit Cup can be seen here: http://faqs.ign.com/articles/387/387658p1.html
Blue Panels (Qualifying Pokemon): 45 Description: Press A when you
highlight this rule, and it will bring
up a list of Pokemon. Pokemon in blue
boxes can be used but ones in red
boxes cannot.
Enter with six Pokemon. Description: Choose six Pokemon before
going to battle. You may not choose
more than one of a certain kind of
Pokemon.
Choose three out of six Pokemon. Description: Out of the six Pokemon
chosen, choose the three that are to
be used in battle. Try to choose the
three battle Pokemon that have
advantages over the likely opponents.
Levels 25 to 30. Description: Pokemon of levels 25 to 30 may be
used. If you don't have six Pokemon,
you may add Rental Pokemon.
Maximum three-Pokemon level total 80 Description: The combined levels of
the three battle Pokemon may not
exceed
80.
Max. HT 6' 8'' and max. WT 44 lbs. Description: The height of Pokemon may
not exceed 6' 8''. Likewise, the
maximum allowable weight is 44 lbs.
Un-evolved Pokemon only. Description: Only un-evolved Pokemon
may be used.
No two Pokemon asleep or frozen. Description: If one Pokemon falls
asleep, none of the others can be put
to sleep by an opponent. The same
goes for freezing. It is possible to
have one Pokemon asleep and another
frozen.
Mew can't attend. Description: Mew may be used only for the Gym Leader
Castle, Prime Cup, and Free Battle.
Get a continue for a perfect match. Description: You earn a
continue for every battle won without
a fainted Pokemon. If you have a
continue, you may try again after
losing a battle.
No Selfdestruct move with last Pokemon. Description: If your last
remaining Pokemon uses Selfdestruct or
Explosion, you lose, even if the
opponent's last Pokemon faints.