Recently after a hard reset I can't use the Google Play Store on my 5.1 Lollipop. Whatever I try to download from the Google Play Store it gets stuck at some percentage and never reach 100%. Plenty of space left in the internal storage, I tried switching between mobile data and WiFi. I've also tried starting a download and leaving it overnight but it just never reaches 100%. I've also noticed that after the reset, sometimes I'm asked to update my Google Play Services even though it has been updated automatically along with Google Play Store. So far I've tried the basics like clearing cache and data of Google Play Store, Google Play Services and Download Manager, rebooting my device, uninstalling updates of Google Play Store and Google Play Services so that they auto-update again since my Google Play Store is useless. I've also tried removing and re-adding my Google account, did another factory reset but back to the same spot. Could it be that the latest version of Google Play Services is somehow incompatible with my device and the device had some old working version installed before the first factory reset since everything was fine until I did the first reset?
Any help would be much appreciated!