On the brand new iPhone 5 sent to me from Apple care.... and they loaded 6.1 in the store. I am getting LTE signal at my desk. I have walled throughout my two buildings at work and have either 4g or LTE. I even have signal in the elevator!! Now I don't know what to think. But at least I'm back in business!!!
iOS 7 won't fix your problem. Unless you purchased the phone directly from Apple as unlocked, you purchased a phone that was hacked to unlock it. Updating it re-locked it. You probably received a warning notice telling you not to update it if you did not purchase it directly from Apple. There is no source other than Apple for legitimately unlocked phones.
If you DID purchase it directly from Apple visit an Apple store or call them and they will make it right.