Verizon and AT&T use different technologies for their networks. You would need a phone that could connect using "CDMA" vs. AT&T's "GSM". You might be able to use another GSM carrier, however. Someone else can chime in on who else uses GSM that a jailbroken iPhone can work on.
Or another Network? Still want to use AT&T's, though. Thanks!