Fixed by sending in for warranty
Just an update...I was having all of these symptoms...unknown IMEI, Baseband, etc...basically gave me an expensive media player for a few months while waiting for a fix on XDA. After no update I decided to call up Samsung and after talking to 3 different technicians, I was able to send it in. Just a note for anyone about to do the same, they will try very hard to blame it on the carrier/SIM card, so save yourself some trouble and just say you already went to the physical store of your carrier (calling isn't enough)and they couldn't get it working. Once you get past that, they will email you a printable 2-day UPS shipping label so you can ship it to them for free. It took 2 weeks from the time I called to having a working phone back in my hands.
This was their fix:
Problem found:
NO PCS SERVICE
Solution:
REPLACED PBA
After a quick search I found that the PBA is the motherboard, so it's definitely a hardware issue. Hope you guys are still under warranty because I've heard this is ~$200 to fix otherwise.
Good luck.