I too was experiencing this exact issue with TimeBroker service crashing and unresponsive start menu after a recent update while having some random clock app installed..
I've managed to solve it by using regedit to set the timebroker service disabled. I then restarted, removed all apps (including Mail, Games, everything) using the PowerShell script. I set the service to enabled and restarted the computer. Then went to store and redownloaded the apps I needed.
Before I did the above I did the old netsh winsock and ipv4/6 reset, and removed all my NICs in device manager, because SSDP service was crashing too. Didn't seem to have any effect. I also ran WSReset, but that kept hanging...
Fingers crossed it sticks :)
How did you disable the timebroker service? I did everything else that you cited, e.g. ran the script and deleted ALL the aps except for the store and IE... and I still have the reinstalled apps hanging due to timebroker hangs.