Okay, basically I want to gather everybody who is having this problem and try to solve it together. Share your experiences and possible solutions.
I will go with mine:
iPhone 3G Black 16GB
Jailbreak with redsn0w 0.8
Unlocked with ulstrasn0w 0.9.1
Reset all settings
No Signal, No service or sarching forever...
Oh, and by the way, I am in Movistar Argentina.
Lets solve this guys.