I'm very happy with VidaOne MyPersonalDiet. It has a very nice interface and I like the way it works with MySportsTraining. It also has a very nice desktop companion you can sync to.

Unfortunately its food database cant hold a candle to CalorieKing. CalorieKing has a database of over 50,000 foods and they add to it all the time. Just about every multi unit restaurant menu item and prepared food dish you can think of is in the CalorieKing database. With VidaOne they just use the standard USDA database which only has around 7,000 entries and almost zero prepared foods or restaurant dishes. The good thing about VidaOne is that it tracks individual nutrients that CalorieKing does not. That being said, unless you go pack to Palm OS, VidaOne is the way to go.