Well as the TIP122 is a darlington pair, you shouldn't have any problem with providing enough current.
However, there are no freewheel diodes in that schematic. There will be a huge voltage spike as the stepper is turned off, which has blown the TIP122.
They could also be wired wrong.