I've jailbroken my wifes 4.1 twice and Cydia still isn't showing??!
Limera1n says its done both times without issue, device turned off and then back on and also hard reboot done to no avail...
No other options than start from scratch again?
Did you load up the Limera1n app on your iPhone and do the Cydia install from there?
I have a 16gb 3GS iPhone. I was running 3.x.x (can't remember exactly maybe 3.1.2)....whatever the latest was with the spirit jailbreak. I did a sync with my updated iTunes on my Mac, and then updated to 4.1 through iTunes as one would normally do. I downloaded Limera1n (v4) on my media PC (connected to my TV) and hooked my iPhone up there, ran it, installed Cydia, restarted, and it's running great. MyWi even remembered all of my settings and my carrier name (changed from AT&T to my name remained as well).