Do you HAVE to give Mr, Pokemon the Red Scale BEFORE he gives you the Red Orb?
When captured or defeated, the red Gyarados drops a Red Scale. While this is the only chance to catch the Red Gyarados in the original games, it will respawn in the remakes after the player defeats Lance and the Elite Four, should the player fail to capture it. -After Defeating Red go to Mr Pokemon -He will give you the red orb (blue in HG) (after giving him a Red Scale, how to be obtained check above) -Go to Cinawood City and go to Cliff Edge Gate -The Gym leader will come and say it impossible to find and you need Surf and Rock climb. -He will let you through -Go through until you meet a place with 2 ladders, go through the one that goes down. -Now go down. -You will reach the sea, go West -In the Rocks their is a gap which you can go through, it hard too see so keep a sharp eye. -Use Rock climb -Battle Groudon and catch it -A man will enter ONLY if you catch Groudon -Go see Pro. Oak and he will tell you something
Sources: http://bulbapedia.bulbagarden.net/wiki/Red_Gyarados http://answers.yahoo.com/question/index?qid=20100409145909AANZmH2