I finally managed to get the updates. Here's what I did (I do not know exactly what helped, but this is all I did).
- Factory reset phone
- Turn ON Find my phone
- Unpin store
- Erase IE history
- Install a new keyboard (any language you did not downloaded)
- After it installs, it will automatically reset the phone. Takes about 10 minutes
- Uninstall the keyboard
- Do a soft reset (volume down + power)
- Re-pin store.
Updates not received immediately. It's been 10 hours until I got the update. I do not know if I will continue to get them, and if it is now fixed.