Simple steps to solve your issues for the jailbreak are –
1. Do a full restore of your iOS device from iTunes and do not put the data back into the device from your iTunes backup.
2. Try jailbreaking using Absinthe. If you’re on a Mac and you get stuck on the “Waiting for reboot…” screen, dump Mac and download absinthe for Windows and jailbreak on the windows device.
3. Be very patient. If your device has data on it, it can even take up to 40 minutes for the jailbreak to work.
I managed to jailbreak my iPhone 4S on iOS 5.1.1 today. All the best to you too!