Hi Jason,
The new claimed sup engine I believe will come with CATOS installed on it. If yes it will difficult to upgrade it with IOS without downtime. Now you have to convert it from CATOS to IOS mode which definetely need a downtime.
However there is a workaround for this problem but nott 100% if that works but you may give a try. The sup engine that got failed , does that failed because of memory issues or any flash failure? If not you can take the bootflash out from that failed sup engine and replace with the new claimed sup engine who will be having the CATOS installed I believe. Now the replace sup engine will be having a bootflash on which Native ios must be installed cause that was running in your old sup engine and you can insert the sup engine in your chassis.
I did that im one emmergency situation where I was having no other option then to take that decision and that worked but not 100% sure if that works in your enviroment because not sure if your old sup failed because of what reason.
Now if the replaced claimed sup engine is coming with native IOS you can simple insert into the secind slot and upgrade it with the image on active sup engine following the steps mentioned in this link
http://www.cisco.com/univercd/cc/td/doc/product/lan/cat6000/12_1e/swconfig/redund.htm#wp1093330
HTH
Ankur
