Are you still using the Samsung Apollo?
Mine used to be flakey with time updates. As you say, go abroad and it did change, but back in the UK it did not always change times. That's on Vodafone.
Apollo now fall back phone as I have inherited a hand me down from younger daughter. Still Samsung, a Galaxy 1, but time adjustment is OK.