Try reflashing your radio & updating the PRL. Install the attached cab if you do not already have the 'Update PRL' option under your settings, and give the new Alltel 1. 03.13 radio a try. I love it. Not guaranteeing this will help, but it couldn't hurt. Reflashing a radio is just like flashing a ROM, only it doesn't hard reset the phone. Check out this thread for radios-
http://forum.ppcgeeks.com/showthread.php?t=74422