Check out our new Sudoku for iPhone:
http://www.freeverse.com/iphone/sudoku/
Give it a try. You can actually play the game in any web browser, it's just sized optimally for the iPhone. :-)
And yes, I have something to do with this: I handled support and release changes to the code, although I didn't write or design the game in any way.
Enjoy!