Windows 8.1 Update 0x80240031

While setting up two new Lenovo E540 notebooks that had Windows 8 on them, I came across an issue with the update to Windows 8.1 via the Microsoft Store.  It would get to 50% downloaded/installed and then error with the code 0x80240031.