I checked the registry and the the "GPSMode" key was set to 2.
I changed it to 1 and rebooted and my GPS is finally working consistently like it should.
Hey this worked for me as well! And yeah, I'm one of those Alltel peeps...
CenFlow, Thanks for posting this.
Also, Thanks to conflipper for the great rom!