While I'm no expert on Android related things, though I plan to eventually do modding and such and just haven't gotten around to it due to college work and such, you can try the following:
Remove your battery and write down your correct serial number, it's printed on the sticker located above the SD Card slot. I say this because in my case my box does not have the serial number on it. The "serial number" by the bar code on the box is actually just the MEID in HEX with some numbers beforehand.
Once you have the serial number boot the phone into the bootloader to use fastboot and try these commands and see if they work:
[HIGH]fastboot oem writeserialno SERIALNUMBER[/HIGH]
[HIGH]fastboot setserial SERIALNUMBER[/HIGH]
If not, maybe providing us with the exact super wipe you used can help us track down a way to reverse the serial number changing as that's probably what did this. Although, like these commands, we may not be able to do anything since it is relocked and now seemingly impossible to reunlock it with this faulty serial number.
Hopefully these commands not only work on our phone and can be used while locked, but work like they should!
Edit: I'm not sure if case (capitalization) matters, but it would probably be best to type all letters of the serial number in upper-case to be on the safe side.
Edit 2: Thinking about it and as I'm not familiar with how they do things or what all they do, it's quite possible one of these is how CDMA Workshop and/or QPST attempt to change the serial, but worth a shot.