The exact verse you quoted in question is found in Shrimada Bhagavatam, Canto 1, Chapter 5
SB 1.5.23 — O Muni, in the last millennium I was born as the son of a certain maidservant engaged in the service of brāhmaṇas who were following the principles of Vedānta. When they were living together during the four months of the rainy season, I was engaged in their personal service.
And its answer is found in Shrimada Bhagavatam, Canto 7, Chapter 15. In some Mahakalpa, Narada was used to be Gandharva having name of Upabarhana. Once he was invited in the assembley of Gods to sing the glories of the Supreme Lord but he sang the glories of Demigods. So, Prajapatis cursed him to born as Shudra.
SB 7.15.69 — Long, long ago, in another mahā-kalpa [millennium of Brahmā], I existed as the Gandharva known as Upabarhaṇa. I was very respected by the other Gandharvas.
SB 7.15.70 — I had a beautiful face and a pleasing, attractive bodily structure. Decorated with flower garlands and sandalwood pulp, I was most pleasing to the women of my city. Thus I was bewildered, always feeling lusty desires.
SB 7.15.71 — Once there was a saṅkīrtana festival to glorify the Supreme Lord in an assembly of the demigods, and the Gandharvas and Apsarās were invited by the prajāpatis to take part in it.
SB 7.15.72 — Nārada Muni continued: Being invited to that festival, I also joined, and, surrounded by women, I began musically singing the glories of the demigods. Because of this, the prajāpatis, the great demigods in charge of the affairs of the universe, forcefully cursed me with these words: “Because you have committed an offense, may you immediately become a śūdra, devoid of beauty.”
SB 7.15.73 — Although I took birth as a śūdra from the womb of a maidservant, I engaged in the service of Vaiṣṇavas who were well-versed in Vedic knowledge. Consequently, in this life I got the opportunity to take birth as the son of Lord Brahmā.
Also the whole story of Narada being a son of maidservant is described in Shrimada Bhagavatam, Canto 1, Chapter 5 and Chapter 6.