Negative times
As far as I know Excel doesn't allow you to store negative dates and times.
Presumably you have some sort of a lookup mechanism to find what the timezone change is, therefore add an indicator such as E or W or whatever to indicate if the time zone needs to be added or subtracted.
If you hold the time zone difference in a cell formatted as [h]:mm you can then use a conditional formula testing the indicator, and either =a1+b1 or =a1-b1