I know quite enough to help unravel this mystery. There was a game released in Japan (Which later made an American release in the GBA) which I think was called Puyo Pop. If you've played Kirby's Avalanche or Dr. Robotnik's Mean Bean Machine, It was the exact same thing. Puyo Pop, however, used these different characters and you played the role of the girl on the box. (and a special tidbit of info, Has-Bean from Mean Bean Machine was actually called Carbuncle in Puyo pop)
No wonder the girl look familiar. This must be some kind of pocket-size adaptation of Puyo Pop
After searching some time in Wikipedia, I came towards this little article;Puyolin the pocket Puyo Puyo
And if you are interested in the game series Puyo Puyo ("Puyo Pop" in USA/Europe);Puyo Puyo Through the Years
Looks like both, the "Dr. Robotnik's Mean Bean Machine" and "Kirby's Avalanche" are actually Puyo Puyo games released in west covered with Sonic and Kirby characters and themes. After those, Puyo Puyos were start to release here under name "Puyo Pop".