Jeff Benjamin tweeted this about unlocking an AT&T phone:
The folks at @cellular_medic are legit. Instant unlock of my iPhone 4S was completed within a few minutes.
http://cellular-medic.com/
I'm might do this for my mom's iphone4 but I wonder if I can lock again after unlocking.