Ok, figured this issue out. However, I am not real wild about this problem happening during the 8.1 upgrade process.
The problem was missing shortcut entries in:
c:\User<user>\AppData\Local\Microsoft\Windows\WinX\Group1
c:\User<user>\AppData\Local\Microsoft\Windows\WinX\Group2
c:\User<user>\AppData\Local\Microsoft\Windows\WinX\Group3
I copied the entries from the non-administrator account I had created, rebooted, and everything is as expected, including windows + x.
I had the same problem after clicking on a wrong website link in a google search. Some kind of PUP virus deleted all these entries, along with everything in the start menu.
Is there a list of which links would normally be there so I can manually recreate them without having to generate a second account?