My three year old loves playing PDAmills SPOT (http://www.pdamill.com/prod_sp.shtml). Most of the puzzles are a bit advanced for her, but she finds the 'find the apple' one seems about the right level. She is also clever enough to know that if she messes up my iPaq I will take her other computer off her and then there will be no more Elmo games :)
TBH, I really haven't seen many kids games for PPC, and I am really not at all surprised.
I have poor expirience in kids games but in my recent searches on mobiletopsoft.com i saw some game packs like Kids Pack 1.3 , Pocket Kid Game Pack and some other games that may be suitable for you and your kid can found at this url : http://www.mobiletopsoft.com/search.php?querywords=kids&order=rel&way=DESC