I also got this message. For me, this is what I think was going on:
The first execution of Lyx very quietly (i.e., in the background) performs package updates for MiKTeX. Afterwards, it actually launches Lyx.
However, if you launch a second invocation of Lyx immediately after the first (since nothing has yet displayed), it will launch w/o the packages it requires and result in the message that you see.
I suppose if MiKTeX was not / improperly installed, you could also encounter this issue.