Now first of all, I assure you, there is not a single issue like mine. Let me list the steps taken with corresponding error messages/new problems to each step taken.
The problem started when the SIM card was changed at a Movistar branch, 3G for 4G. Mind you, the phone is brand new, 2 months on it.
iPhone continually searches for signal "Searching...".
a. Attempted to soft reset iPhone, with/without SIM card. No visible effect.
b. Removed SIM card and it was not installed again after this point. Attempt at a Hard Reset from Settings in iPhone (Erase all content and settings) Strangely, apps+contacts were not erased. Attempted again. No visible effect
c. Attempt at a iTunes managed complete factory setting restore. Newest iOS as of Today, 15 minutes ago.
After step 2a the iPhone prompts a "connect to iTunes" message. There is no functionality enabled. It stays in this state throughout the rest of the steps.
a. New problem. During restore an error was encountered (Error 1). Progress bar freezes for 3 hours, finally decide to disconnect it.
b. Attempt it again after downloading and installing new Windows updates(Restarted computer), same results as mentioned with slightly different error message (Error -1)
a. Attempt to install earlier version (iOS 8.0). (Error 3197) Failure.
b. Fix Hosts file in respect to what Apple support says about the error. Disable Firewall, attempt to install iOS 8.0. Same Error.
c. Attempt to install latest iOS, new error (Error 1671).
d. Read similar question , followed the top answer's guide to putting iPhone in DFU mode and only then restoring. Recieved same error as step 2a around the same part of the progress bar. This was the point I gave up.
Special thing about this error (Error 1671) is that it does not appear among the specified "unknown" errors on Apple support page. It is a new kind of unknown altogether.
Back the the question, How do I fix my iPhone
iPhone 5s (GLOBAL) A1533