Getting the same message on my (unrooted, but unlocked) Telus Milestone... Have had it for a grand total of three weeks. Changed the battery on Thursday and when I tried to turn it back on, got the "code corrupt" message.
Thinking back on sequence of events, I suspect it's because I failed to power off the phone before switching batteries. I was running Flip Silent and felt it vibrate to tell me it was changing the ringer state just as I popped the battery out. (A moment of "uh-oh, maybe I shouldn't have done that".) Also was an eBay battery that I had removed... Motorola holograms on it, but closer inspection shows no water indicator stickers so thinking it's probably a counterfeit. Not sure that should really have any bearing on it, but maybe...
After trying (unsuccessfully) to restore with the Motorola Software Updater I called up tech support. Was expecting them to tell me "tough luck, it's unlocked", but they gave me an address to send it in for warranty repair. Guess we'll see soon enough whether they can (will) do anything for it... Seriously disappointed to be back to my old Blackberry for now, though.
Any suggestions on other possible fixes if the repair depot won't touch it? I can't get to the Recovery screen, so not sure what my options are from this point if they tell me "too bad".