The issue for me was related to having used CCleaner and/or Disk Cleanup Manager (Cleanmgr.exe) to remove leftovers of previous Windows 8.1 installation. This had removed the files but not properly removed registry traces of the previous installation that were still available to Windows Update (and in fact "Settings -> Update & security -> Recovery -> Go back to Windows 8.1" function was still available, even if non-functioning). In this condition, the 31 days upgrade protection mechanism was probably broken. This might be a bug in Windows Update actually.
The following registry file removed for me the traces of Windows 8.1 previous installation (also hiding the "Recovery -> Go back to Windows 8.1") and enabling the 1511 update. Be prepared to a very long update process (>4 hours for some users). For me, the 1511 update stalled at "Preparing to install updates 32%" for at least 2 hours with OS installed on a SSD storage. For your security, backup before applying the registry edit.
Windows Registry Editor Version 5.00
[HKEY_LOCAL_MACHINE\SYSTEM\Setup]
"Upgrade"=-
"UninstallActive"=dword:00000000
"UninstallMark"=-
"UninstallGUID"=-
"UninstallSourceVersion"=-
"UninstallScenario"=-
[-HKEY_LOCAL_MACHINE\SYSTEM\Setup\Upgrade]
; Adapt following key to the one actually present in your registry
[-HKEY_LOCAL_MACHINE\SYSTEM\Setup\Source OS (Updated on 8/16/2015 11:36:09)]
A similar advice to resolve a different kind of problem was given in this post in a user comment (hutsy).