Resolved
I finally got the the updates to work by disabling the UAC by going into the regedit, make a registries backup and updating the following:
HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\
CurrentVersion\Policies\System\EnableLUA to 0.
At this point, Windows update started to work.