I went through all the troubleshooting steps in the "Update Available From Sprint" thread, making sure I was on v1.29.651.1, yada yada. Worked on this for a week and a half. Spoke with Sprint, spoke with HTC, no luck. Going to firmware update always reported NO UPDATE AVAILABLE.
Took the phone back to Best Buy and demanded an exchange. After receiving the new phone, went to try to firmware update, it showed that one was available. I asked for my old battery back since it was charged fully so that I could do the update. Put my old battery back in, went to update, NO UPDATE AVAILABLE!
Turns out it was my battery? Put the new one back in and the update was successful. I had scoured the net before but did not notice anyone with this particular issue. I hope this helps someone.

 

Thanks Nick!
I tried and tried and tried (did I mention that I tried?) no less than 50 times conservatively. Tried factory resetting, loading the factory ROM, nothing. Until this battery thing. I really think there is something to it. Thanks for your input!