I've been playing this for a while now as a barbarian, and I quickly found that the game is too easy, even on the hard difficulty. I'm surprised that Gamespot's review didn't pick up on this, because Puzzle Quest 1 was also too easy in my opinion. Anyway, I decided that I had to increase the difficulty myself if I was to carry on playing. So I decided that as well as playing on hard difficulty, I wouldn't have any armour equipped at all (although I would still have the best weapons and spells equipped). This has definitely increased the challenge, making the game more fun to play.
I would be interested to know if anyone else has done anything similar, particularly with the other playable characters, as I've heard that the game can be more challenging anyway when playing as the other characters.