The Lubavitcher Rebbe zt"l explains (in Likkutei Sichos 15:339ff; English adaptation at Chabad.org) that there was one detail in the dreams that threw off the magicians.
The Torah describes the first seven cows coming out of the river, and then the second seven cows, "and they stood next to the cows at the riverbank." Now, times of plenty and of famine come sequentially; there's no time when both are present. So this forced them into alternative explanations, such as "you will father seven daughters" - from one of your wives - "and [at the same time] bury seven others" born from a different wife.
Yosef's insight, then, was that indeed the two could coexist. If the surplus from the good years is stored away for the famine, as he suggested (thus also incidentally answering the question of how he dared to advise Pharaoh when he hadn't been called to do so), then throughout the first seven years, the upcoming famine will be very much present in everyone's minds. Conversely, during the seven years of famine, the years of plenty will still be present - in the form of the grain that they produced.
(It's interesting, though, that in Pharaoh's retelling of the dream to Yosef, he just says that the skinny cows "came up after them" (41:19), without mentioning that crucial detail that all fourteen of them stood together for a while. If he also omitted this detail when talking to the magicians, then that still begs for the explanation of why they needed to account for it, and why Pharaoh didn't find their answers convincing.)