The source for this story seems to be Shalshelet Hakabbala (p. 104 here). He says he heard it from an old man who saw it written in an old book.
The relevant part of the story is:
וזה הרמב"ם היה קשה ההבנה מאד ומעט רצון היה לו בלמוד
This Rambam was very hard of understanding, and had little desire to learn.
The story is quoted almost verbatim in Seder Hadorot (source found by hazoriz).
The book Hamore Ladorot by Me'ir Oryan (source located by Tamir Evan) quotes the legend, but judges that the true core of the story is probably limited to the part of the story about the Rambam going to learn from Rabbi Yosef Ibn Migash, implying that in his view the line about the Rambam being hard of understanding might have been an embellishment.