How can I change the SID of a user account in the Active Directory?

You can't. You have to do an authoritative restore of the user account in order to get a user back. Have a look at this Technet article.

I know this question has been answered, but for the future you may also look at the tools out there like Quest's Recovery Manager for Active Directory. If you have a system state backup it can recover the object without a reboot of the DC. They've been known to work with folks in a situation like yours to try and get you up and running in hopes of getting a sale. Better, though, is to already have it licensed and in place in case there's a major issue, like someone deleting an OU or something drastic like that.