M0 (zero) does not turn the spindle off on my machine either. You might try an M6 command because the spindle has to be stopped for you to change tools.
When I use multiple tools I always use a M5 and a M9 to turn off the spindle and the coolant.
My program will read something like:
Z1.0 to pull the cutter away from the part, then M9 (coolant off), M5 (spindle off), M998 (move to tool change position, T? (tool number) M6 (tool change).