Predictive power is necessary, but not sufficient.
I don't agree that it's "the most fundamental criterion", because it's not a matter of weighing various criteria, some more important than others, and saying "yep, this theory is good enough, it's a keeper". Instead, all of the criteria must be met. An explanation must make verifiable predictions, those predictions must be borne out, the explanation must not be easily variable to accommodate any observations and must imply its own reach.
As to your example, QM doesn't say that systems only behave quantum mechanically below a certain scale. They behave that way at all scales... it's just that at larger scales the collective probability of observing the quantum "weirdness" is so low that it effectively never happens. At least in most cases: Young's experiment shows that QM behavior can be quite apparent at larger scales.
FWIW, I don't consider QM to be an ugly theory at all. In particular, I find the many-worlds interpretation of QM to be quite elegant and beautiful -- though still quite brain-twisting and very different from our common conception of the world. But then, frankly, classical atomic theory is also quite alien to our common conception of reality. For example, the notions that solid matter is nearly all empty space and that the fact that we can't walk through walls is actually due to counterposing fields not because the matter of my forehead and the wall really "collide". The notion that we live on a spherical body rotating around the sun is also quite counter-intuitive, frankly. It only seems clear and obvious because we're used to it. So degree of match with human perceptions of reality isn't really a useful yardstick.
Interestingly, I think beauty and elegance are useful yardsticks, though, because they tend to bear precisely on the "hard to vary" characteristic of good explanatory theories. The more complex a theory the less elegant and beautiful it is, and the more "knobs" there are to tweak to explain different observations. Current explanations of subatomic particle physics are deeply unsatisfactory... and not only are they ugly, with their explosion of seemingly random types of particles, we don't have explanations that tell us why we observe all of those particles and not others or (with some exceptions) what all of the other particles may be. This lack of reach and excess of variability indicates that we don't really have a scientific explanation of subatomic particle physics, even though we can make some predictions.