I've found that yes, if the "sync" is checked a lone train doesn't leave the station. And as far as I remember it's always been that way. (I may be wrong, it wouldn't be the first time). With your scenario, I always uncheck it, then as soon as the first train starts to leave, I check it again and things go as they should.
If I have say 8 trains and 2 stations, I leave sync off for 4 trains, then as the 4th is leaving I check it again, and they sync up as they should.