I suspect you are going to need a software reload or upgrade. I have a few machines that will not Restart correctly and I finally gave up trying to get them sorted out after about three software changes. Some are production machines so not being able to Restart is not a big deal.
It is possible to restart with the Program Restart Setting turned OFF and I do this when needed. You do need to be careful because the machine will fire up immediately and do whatever is on the line you start at.
My procedure is to step up to the first motion command after my start point in graphics and make a note of the machine coordinates. Then jog the machine to that location and start immediately before the tool change as you are doing. Have single block turned on also.
An open mind is a virtue...so long as all the common sense has not leaked out.