GNOME Sudoku is a particularly good Sudoku game, which is now included as part of the gnome-games package. Since Edgy, it's certainly seen a lot of polish. There are far fewer bugs, some nice new features and even a touch of eye-candy here and there.
The screenshot doesn't do all of the improvements justice. For example, if you click twice on a square, a keypad pops up so that you can select a number without touching your keyboard. There's a highlighter (in the screenshot), and even a couple of text entries at the top and bottom of each square for you to note-down possible numbers in.
If you're a hard-core Sudoku nut, upgrade to Ubuntu Feisty.