1. Did you get all CDs(as an item)
2. Did you get all on "challenges".
I just had to unlock Green Greens by playing as Kirby 20 times, that's all. This topic has been solved for a few days I just forgot to report back here.
Green Greens was the only stage I didn't have because I never use Kirby. I had all other characters, stages and modes in the game but it. I used my SSBB strategy guide I got the day I bought Brawl, and it said you have to unlock all Melee stages. I just used Kirby about 10 or more times in 3-stock battles with a computer just so I wouldn't waste my records; it felt like forever. I also unlocked Mach Rider, Princess Peach's Castle (Melee) and the ability to choose what stages Random picks upon unlocking Green Greens.
If you think about it, it took me two years to unlock Green Greens because I had this game since nine hours after its release. Kirby is just one of the most unused characters in my game so that explains it.