This worked for me, give it a shot:
Trying to return the vehicle to stock in the normal manner will fail, but I can return it to stock tune by: trying to again download a custom tune, turning the key off as it updates (resulting in a download error), the tuner asks to return to stock, I accept and the update works successfully. The car will then start, on the stock tune.
Mine: 2006 Mazda3 s GT Hatch: 115k, Gray, Manual
Gone: 2002 SVT, #1654
Hers: 2012 Focus Ti Sedan: 55k, SGM, Manual