I was astonished to discover that in fact the reason the start "All Programs" was blank, was that windows can only display a certain number of program files.
After installing yet another program, the same thing happened again! So I opened c:/ProgramData/Microsoft/Windows/StartMenu/Porgrams/, made some category folders, moved some files over to the new category folders and problem solved