And now it's magically working. I think, best guess, that (at least for Verizon) you MUST turn on Location Services - this one's pretty obvious - and the best way to do that is through QuickGPS... then it seems like you have to be out in the wide open the first time to get it to "wake up" and then you're good.
OTOH, maybe the next time I try it I'll be dead in the water again...