You have 3 different possibilities:
1.)
Make a stereo roughmix of the song.
Try to stretch this one, but I'm pretty shure, that the tempo difference from 129 to 112 is too big. But you never know, maybe the band likes the sound. If so, mix proper and stretch the ****.
2.)
Take Abletons LIVE 5, (it's out since a week or so,
http://www.ableton.com/) they have the best tempoalgorythms I heard. You can export all your single tracks into Live and then edit the Time Markers (called warp points) in each track. Now you can change the tempo of the whole song. Good luck !
3.)
Get them in the studio and let them play again (which I would do)