This is a very interesting concept, and I can falsify it with little effort within the context of music specifically.
I can and do construct pieces of music out of simple understandable elements, with simply described relationships, that are incredibly difficult to process or extract when listening to them.
They do actually talk about this idea in the talk. The "shortest possible program" that can be used to describe the music is undecidable, but there is a short description, in the case you just described it's unknown to the listener.
I can and do construct pieces of music out of simple understandable elements, with simply described relationships, that are incredibly difficult to process or extract when listening to them.