Have you checked the timezone settings on the iPhones that have a problem?
Settings => General => Data & Time
Also as you said I would recommned that you do the software update.. As far as I know there are no bug fixes for this from 2.2 => 2.2.1 but doing a full restore can always help..!