Hope this helps
Ok, I'm no expert on jailbreaking, but here's my suggestion...
What version of redsn0w are you using? The latest out is 0.9.10b5 make sure you're using the most up to date version.
Next I think it sounds like you're getting just a partial jailbreak and install of Cydia done, you need to try doing something else than probably just pulling in and going through maybe.
Are you using a mac or pc? Either way I believe redsn0w has the same prompts, (I use mac). Oh and first things first connect to iTunes and do a backup in case you run into any issues.
What you should try doing is downloading the most recent version of redsn0w, and the most recent iOS for the phone 5.0.1 from Apple. Save the iOS file somewhere easy to find like your desktop or something.
Open redsn0w, click on "EXTRAS" then click "SELECT IPSW" and point to the iOS file that I mentioned putting somewhere easy to find.
Now hit "BACK" then jailbreak and "Install Cydia" should be checked.
It's really easy, and there's tons of walkthroughs that are really good here or if you google it, and lot's of people on the forum will help you.
Good luck!
Oh and I just thought of this, when you do your backup on iTunes, try doing a restore as well and starting fresh, it probably wouldn't hurt.