It would take years before Pharaoh could know if any of Joseph's fat-thin cow dream interpretation was accurate. Why then did Pharaoh make Joseph 2nd in command in the country immediately? Were things going so badly in Egypt then that the Pharaoh needed a new 2nd in command?
I heard the following explanation from R' Rivlin, Mashgiach of Kerem B'Yavneh (although I'm sure it's found in earlier sources somewhere):
Pharaoh had a dream in which there was a startling heretical image - he was standing on the chief god of Egypt, the Nile (Bereishis 41:1)! When he related this dream to others, he wanted to hide this point, and so he related as him standing on the bank of the Nile, not on the Nile itself (Bereishis 41:17). However, Yosef informed Pharaoh that he had actually been standing on the Nile itself in his dream, not next to it. This is hinted to in Tehillim 81:6, in which the verse (homiletically) reports that Yosef was "unable" to hear the word "sefas/bank" in his becoming leader of Egypt. Therefore, Yosef showed that he had "inside information" and his interpretation was accepted.
A similar idea (without the clever reference to Tehillim 81) can be found in Medrash Tanchuma 3, in which the Medrash contrasts all of the discrepancies between what Pharaoh actually dreamed with what he told Yosef. Yosef told Pharaoh that G-d would provide the answer (Bereishis 40:16), at which point Pharaoh changed things in order to test him. The Medrash relates that Yosef called him out on each one (the Medrash actually leaves out the aforementioned, about the bank of the Nile). Realizing that Yosef was getting his info from G-d, he accepted his interpretation and appointed him as viceroy.
"Let My Nation Descend" says that Paroh also dreamt and forgot the interpretation, and he was hoping that someone could jog his memory. He knew Yosef's was correct because he recognized it.