sequel was coming out for some time -- turns out, we've known longer than we thought. In April 2007, D3 Publishers announced Galactrix, a "blend of puzzle, RPG, and strategy games" with sci-fi twist. This week at GDC, D3 announced it again (via Gamespot), only this time re-branded as Puzzle Quest: Galactrix. (You can view the old screenshots here.)
The obvious gameplay difference from Puzzle Quest is the hexagonal board, adding to the board's complexity. Galactrix is due out this year for DS, Xbox Live Arcade and PC; a PSP version could not be confirmed.