How deeply into the new time zone have you gone?
Your phone gets the date and time from the cell tower it is connected to; if it is still connected to a tower in the other time zone or, if it is not connected to a tower at all, then it won't have the correct info.
Are you on Sprint? If so, you may need to run the profile update function.