What recovery are you using? It sounds like it isn't wiping everything properly. You can use a Obijohn's update wiper to ensure that there isn't any junk data floating around in there. Here's a link to it...
http://www.mediafire.com/?bh5i7grngo7cvc1
Flash it in recovery just like a rom.