So, as it turns out, my issue came down to my Mobile phone. It had the Authenticator on it and it seems at some point for an unknown reason, Internet TIme sync had been turned off on my Phone. This resulted in some clock drift on my Phone, some where between 6 to 30 seconds. Apparently anything more than 6 seconds is enough to cause the 2FA codes to fail validation.
So the Time zone changes we tested early on seemed to be a bit of a false positive in our testing, not sure why this worked for a short time.
Overall the resolution has been re-enabling Internet Time sync on my phone & 2FA now seems to be working fine.