I'm a newbie when it comes to programming, but I believe the AccelStepper library is controlling each wire of a 4 wire stepper separately. I see it is using millis() for timing... As joe mcd points out, the Allegro A4982 driver chip (or the A4988) make all the difference. All they require is Step and Direction signals. And there are a number of ways to provide the Step signal at higher speeds.
Especially if you go for one of the 32 bit faster ARM processors like the Teensy 3.0, which is only $19, BTW, for 48MHz, much kinder on your budget.http://www.pjrc.com/store/teensy3.html
Teensyduino is almost entirely compatible with Arduino Sketches, or you can use full on C/C++ to program them.http://www.pjrc.com/teensy/teensyduino.html