The only Microsoft supported method to change the SID of the computer is to run sysprep with the /generalize option
edit: So.. clarifying. This goes back to the idea that the computer SID really doesn't matter (except for domain controllers) because it's really the computer account SID in the domain that matters and not the computer/machine SID itself. Removing/deleting/Rejoining the computer will create a unique computer account SID in the domain and would really resolve his issue. But it would not, in the technical sense, create a new SID for the computer itself.
Mark Russinovich discussed the unique machine SID "myth" and there is a follow up article by a different author that goes into additional detail. Finally, there is this MSDN post that, I find, illustrates the machine vs domain computer account SID pretty clearly.
Personally, I've run into the duplicate SID issue where a cloned system was used to create the Domain Controller for a new domain at the start of a domain migration project and the servers in the source domain were not able to authenticate users on the new target domain or join the target domain due to the SID duplication. So, 99% of the time, it doesn't matter.. but when it does matter, it sucks. As a result, I still recommend users generate new machine SID's when they are able to.