That could just mean we're no good at solving mysteries that involve magic.
Also, I think there is a selection effect in so far as there are solved mysteries where the solution was magic; however, you'd probably argue that they were not solved correctly using no other evidence than that the solutions involved magic.
It depends what you mean by magic. Nowadays we communicate by bouncing invisible light off the sky, which would sure as hell qualify as "magic" to someone six hundred years ago.
The issue is that "magic", in the sense that I take Minchin to be using it, isn't a solution at all. No matter what the explanation is, once you've actually got it, it's not "magic" any more; it's "electrons" or "distortion of spacetime" or "computers" or whatever, the distinction being that we have equations for all of tho...
Here's the new thread for posting quotes, with the usual rules: