I had a similar problem with the adafruit motorshield, their bus speed is too low and can't run 2 stepper fast at all. I would recommend the A4988 as stated above. I realize you said you are stuck with the shield, but frankly I learned the hard way that those shield really are not that useful. Are you looking for higher speed (rpms)?