Do they have a store?
Go to the store and ask to see 4G showing on one of their phones. (Even a sales associate's personal phone is fine.) If yours doesn't show 4G at the same location, you have a bad phone. If theirs doesn't show a 4G signal, they'll be on the phone (with their tech people) before you can ask what happened.