Here are the steps I followed, Was JB on 6.1 and just JB 6.1.2.
I updated to iTunes 11.0.2 first, then restored my JB'd 5 to original state 6.1.2, then was able to re-JB with evasi0n, launch Cydia to prepare the JB filesystem, then restore my phone from the backup I had just taken in iTunes.
After the restore, none of my apps that I had from the app store (30 or so) are on the phone.
I updated to iTunes 11.0.2 first, then restored my JB'd 5 to original state 6.1.2, then was able to re-JB with evasi0n, launch Cydia to prepare the JB filesystem, then restore my phone from the backup I had just taken in iTunes.
After the restore, none of my apps that I had from the app store (30 or so) are on the phone.