Are you sure that the iPhone isn't bought with a AT&T simcard/contract in the first place? If so, it should be working just fine... Well as long as you have an Edge-signal on it.
Otherwise jailbreak with blackra1n and unlock with BootNeuter from Cydia. And make sure that you have OS 3.1.2 on it