I'm not sure how the stepper library you are using handles things, but could it be that there's just not enough time gap between pulses to fit both in? As in when motor 2 pulse is being sent, it's blocking at the time motor 1 pulse is required.
A logic analyser would show you exactly what is going on.