I don't remember much- Something about a genie escaped from captivity to cause some catastrophe and the hero (player)'s goal was to undo it. I'm fairly certain it was made for the Gamecube, and the commercial for it showed a scene of a minotaur in armour and carrying a battleaxe charging toward the screen.
You're describing Dark Cloud, released for the PS2 in 2000/2001, but not ported to the Gamecube.
Dark Cloud tells the story of a group of adventurers who band together to fight against the Dark Genie, who has attacked and destroyed many villages. The main protagonist and player character is Toan, a boy who is given a magical stone called the Atlamillia by Simba, the Fairy King, granting him the power to rebuild the destroyed lands.