I am also on Alltel and was having trouble with my gps not working. Try this post
http://forum.ppcgeeks.com/showthread.php?t=36377. After I did this fix my gps still took about 10-15 seconds to get a lock, but at least it works. Just make sure you are enabling your location in phone settings or else gps will not work. Hopefully this helps..