Like gem puzzle games but are tired of all 4589 of them? Give Puzzle Quest a try -- a very refreshing take on the style.
It combines the normal "match three or more" gem puzzle into an interesting "battle" scenario, utilizing things such as magical spells you can cast, colored "mana" you collect to cast the spells, and damage you can wield on your opponent via other matches. As you battle, you collect coins and experience points, both of which can be used to "level up" your gaming character as you work your way through the [typically cliche, but workable] story. As you buy equipment and improve your stats by "leveling up", you character will become more proficient at certain combinations of matches, doing more damage to the enemies you face.
Puzzle Quest is available for almost every gaming platform, from phones to the Wii to the PS2, and plays identically on all three (I've played the PC version, and own the 360 and PS2 versions).
Nothing Earth-shattering, but for a guy like me that had tired of the "formula" of puzzle games, this has been a very fun ride.