I'm not sure if that fix in fact works for Alltel's 1.12.20F? At least it isn't for me. I believe I will change radios.
Edit: I just searched for 'GPS' within the stickied radio thread and this seems confirmed all over the place, the registry change works for Sprint's 1.12.34F but not Alltel's 1.12.20F.
I just switched to 1.12.34F and GPS went from non-functional to ~8 locked SATs within 11 seconds (I timed). Win!