IIRC, any smart playlist that uses "most" or "least" (as in "most often played") is broken in that it works inversely on the iPod Touch/iPhone.
For example, "25 most played songs" actually shows you your 25 least played songs (when the playlist is put on the Touch/iPhone).
Until this is fixed, if you want your "25 most played songs", make a new smart playlist that shows your "25 least played songs". Once you sync it, your Touch/iPhone should show the "25 most played".