Okay so now, I did a factory reset, it works. BUT, I can't sign into Google. Each time I try I get the "There was a problem communicating with Google servers" message. I tried with 2-step AND without 2-step. Doesn't work. So my phone is pretty much unusable now without a Google account. Anyone have any ideas about this?
EDIT: Also, about the Play Services, I did mess with it, but that was a couple of months ago. I tried to do something stupid, and lost the Play Services completely, so I had to manually install the APK for it. The System Update thing went missing only a few days ago.