The plot thickens: I made an appointment for the Apple Store for Monday to do a swap.
In the meantime, two members of my staff updated their iPhones and are now having the exact problem. I watched one of them do it--he never had a 3G signal here before, and now keeps reverting to it.
I've talked to Verizon and they are escalating. I no longer thing a replacement will fix this problem.
Very strange that others aren't seeing the same, but everyone here who has upgraded is.