Moving on, I had a stock Galaxy S4 i9505 on 4.2.2, locked to Portugal's Vodafone (I now understand this is probably what caused my issues).
I wiped data, cache, and flashed the Google Play Edition ROM. When the phone booted, I had no network, even after inserting the PIN number and going through the setup process. So I went to the Network Carrier selector in the Settings (Settings More - Mobile Networks - Network Operators) and selected Vodafone from the menu.
Then I got network. For 2 minutes. Then no network again, until I repeated. So this was driving me nuts, and I Googled what to do, and found out I could use an app called "Network" to try and switch from WCDMA to CDMA. So I downloaded that app, changed my network (to something - I don't know what since I can't open the app, as it crashes every time), and I'm still with the same issue.
Flashed back stock image and restored nandroid backup - nothing helped. Any solutions?
TL;DR: GS4 Locked to Vodafone -- Flashed GPe ROM -- No Network -- Flashed Stock -- Still no network
EDIT: I actually didn't quite flash back to where I was before, so I can't get my Nandroid backup to work (bootloop); I was on 4.2.2 stock, ended up flashing 4.3 stock since I couldn't find a 4.2.2, so my backup doesn't work.