It doesn't sound like a phone problem to me either. It sounds like the building. I can see the same thing at many malls. I can have 3 bars and then walk 20 feet and have no signal. At the local Lowes, it depends in which aisle I am in and what types of products are in those aisles. If 3 phones did the same thing then it is not likely the phones.
Isn't that a stinker? All the advances in the technology and they still have issues getting signals into some buildings. I wonder if LTE will have better luck.