I'm having the same issue. I've got it jailbroken. I've installed ultrasn0w and tried everything you've described in this thread. My carrier is also reporting carrier 8.0 which I thought was odd. I've also tried my tracfone sim and here's a REAL interesting bit: after inserting the TRacfone sim in the iPhone, I get notification that I have 2 voicemails (which I do) but if I go to check the VM, it says no service and remains no service.
Now I've uninstalled Ultrasn0w with no SIM card in place, rebooted the iPhone. Reinstalled Ultrasn0w, shut down, inserted the SIM, and rebooted again. STILL no service. BUT when it comes up, I get the "Waiting for activation This may take some time." screen.
Somehow I have a feeling it's got something to do with that activation screen...
I suggest going to 4.0.2 or 4.0 and updating to 5.13.04 like me. I have 4.0 3G 5.13.04 no problems. Just shift restore. 4.1 isn't much better than 4.0.2 turn off multitasking.
Not to be intrusive but you should probably remove the pic or repost with your IMEI blurred out. It's not safe to have that info floating around the net.
There is currently no going back once you go to BB 6.15. Even with the 5.08 loader you still can't drop down again (wish I had known about fuzzyband BEFORE I went to 6.15...).