How should I treat this prior work?
Options:


Ignore the newly found paper for now. The result would be the same as if you learned of the paper just after the conference rather than before. Downside: People might get a chuckle over your lack of knowledge of prior art. Someone might point out the prior work at the conference if you don't mention it there. Some might think you plagiarized. However: You did the work in good faith and submitted in good faith. 
Inform the conference chair of the issue and ask for advice. Tell them you can add a note about the recently found paper OR you can do a rewrite incorporating the old work and emphasizing your own contributions. This assumes there is time and process for rewrites. Downside: The chair may withdraw the paper or just let it go, again assuming good faith. However: You clearly show due diligence. 
Withdraw the paper and rewrite it for the future. Downside: You don't get a publication just now. However: Time can also let you rethink and possibly extend. 


The sticky wicket here is that it was the most important theorem that was previously proven, leaving you, perhaps, with less novelty.