Alright, I couldn't let it this go, so I tried several things. Upgraded the radio: alltel 3.37.2 (didn't do much), then tried sprints 3.39.10 (also not much help).
So, I decided to go back to stock alltel (2.14.### Radio 1.40) and upgrade to the new Alltel ROM and Radio together (3.35.67 Radio 3.37.2). That helped a lot and I still haven't even played with the settings yet.
