Just for the record:
- the original remote showed no different behaviour
- reset to factory settings via the menu (not the hardware button) fixed the problem
My 1st generation WD TV Live now start within a blink of an eye, as before the update. Everything is fine now (except for the age-old problem of random play still being non-random, of course).