Your reasoning makes sense if you take the same route back on which you came.
However, in Sebastian's case, he made a complete trip around the globe twice, so he crossed the dateline twice without crossing it back in the opposite direction. Meanwhile, he forgot to set his watch back.
JOHN: Two trips around the world this month. You didn’t ask his secretary; you said that just to irritate him.
(Sherlock smiles but doesn’t respond.)
JOHN: How did you know?
SHERLOCK: Did you see his watch?
(Brief flashback to Sherlock looking at Sebastian’s wrist as he scratched his neck.)
JOHN: His watch?
SHERLOCK: The time was right but the date was wrong. Said two days ago. Crossed the dateline twice but he didn’t alter it.
So he had to be travelling west across the International Date Line (IDL) twice:
Crossing the IDL westbound results in 24 hours being added, advancing the calendar date by one day.
Why not travel the same route back east?
There can be several reasons:
The op correctly noticed that if Sebastian never changed the watch at all, it would show the correct date. The watch does not really care about travel or datelines, and time went on normally for the watch and London (relativity effects omitted), so without any change on the watch the date and time would be correct again after the travel. So he must have changed the time without changing the date, that's what lead to the problem. That is an easy mistake to make, because it is common knowledge that you have to adjust your watch to the local time, but you only ever have to adjust the date when you travel over the dateline.
Sherlock further deduced that it had to be within a month from the fact that the watch was relatively new:
JOHN: Within a month? How’d you get that part?
SHERLOCK: New Breitling.
(Flashback close-up on the watch showing its brand name: Breitling Chronometre Crosswind.)
SHERLOCK: Only came out this February.
Fun fact: Sherlock was wrong about the last part, the model of the watch has been out for years:
The one thing Sherlock got wrong! [..] The model featured is a Breitling Crosswind, popular for many years but no longer in production. The nearest equivalent is probably the Chronomat.
Of course this might be different in the Sherlock universe.