I'm having the same problem as Ganeshx. I did the jailbreak on my ipad with no problem, however, after I did the jailbreak on my iPhone 4 Cydia itself won't open. I try to open it, and it closes right away. If you try to re-jailbreak, absinthe says the device is already jailbroken. I've tried doing full resets and restores with no luck. Erasing all the data on my phone, nor a restore is removing Cydia.
So long story short, Cydia won't open. I can't reinstall Cydia via absinthe, and I can't remove Cydia with restores or resets. Any ideas?
EDIT: I reinstalled the firmware via iTunes. Cydia is now gone, but absinthe is now saying that the device is unsupported
EDIT 2: Ok... I think I mucked it up now. Just read that Apple pushed out a new update for the iPhone 4 (5.1.1 (9B208)) earlier today. Safe to guess that this is the reason why absinthe is now saying my device is unsuppoted. So take that as a warning.
EDIT 3: (Last edit, I hope). I was able to download and reinstall 5.1.1 (9B206) since Apple is still signing it. Absinthe detected, installed, and everything works.