How are you installing the different versions? Do you use Rom manager or do you do it through recovery? If you've only done it with Rom manger, try Recovery.
Do you just flash the rom or do you factory reset, then flash the rom? If you haven't tried the complete wipe then a fresh flash of the rom, try backing up stuff to your sd card (with something like Titanium Backup) and and then factory reset, clear data and such, then flash the new rom (and gapps).
I'm just throwing out ideas (if you haven't tried these already). Also, you might want to try downloading the new rom again.