As CDR points out in an earlier answer, the first description of Naidu as a nightingale comes from a review in a British newspaper of her first volume of poems, The Golden Threshold (1905). However, the review calls her "an Indian nightingale", not "the nightingale of India". Those are rather different, the latter being generally descriptive rather than a specific epithet. And as Charo notes in her answer, the more specific reference to Naidu as "the nightingale of India" is generally attributed to M K Gandhi, with whom she was closely associated. Usually, it is said that he referred to her as "Bharat Kokila", which is then said to translate to "The Nightingale of India." The question mentions "Bharatiya kokila", but the term commonly used is "Bharat Kokila", as a ritual invocation of Google shows. The Google search also brings up many web pages that say "Bharat Kokila" is Gandhi's. But this claim never comes with any specific citation. Gandhi certainly used the phrase, but was he the first to do so? It's debatable.
The term "nightingale" itself needs some interrogation: what bird is being referred to here? Nightingales are not native to India. "Kokila" is the Indian cuckoo or koel. CDR also references "Bulbul-e-Hind"; the bulbul is yet another bird. What all these birds have in common is song. The koel and the bulbul are associated with sweet music in India, just as the nightingale is in the West. This association means that someone translating "Bharat Kokila" or "Bulbul-e-Hind" might easily choose "nightingale of India" as the equivalent.
In other words, whether the reference to Naidu as "the nightingale of India" originated in that specific form is as debatable as the claim that it originated with Gandhi. It might have originated as a translation. As a phrase, "Bharat Kokila" could in theory be ordinary Marathi; one of Naidu's mentors, Gopal Krishna Gokhale, who urged her to use her poetic gifts to advance the freedom struggle, spoke Marathi natively and might have referred to her in this way. It is however much more likely to be highfalutin Hindi. "Kokila" is rare in ordinary Hindi. The usual term is "koyal", whence koel. But as an epithet, "Bharat Kokila" carries more dignity, being Sanskrit-inflected. "Bulbul-e-Hind", by contrast, is Persian-inflected, and so would carry dignity as highfalutin Urdu. (Hindi and Urdu are mutually intelligible registers of the same language, Hindustani.) Naidu was associated with the court of the Nizam of Hyderabad, since her father was a high-ranking official there. She was therefore well-versed in Persian. The Nizam was impressed by her poetic talent, and the epithet "Bulbul-e-Hind" could have emerged from his court.
It is even debatable whether "the nightingale of India" was originally a reference to Naidu's poetic talents at all. Makarand Paranjape quotes Izzat Yar Khan quoting Naidu's brother Harindranath Chattopadhyay:
Sarojini came to be called Bulbul-i-Hind, the Nightingale of India, not, I am convinced, because of her verse, but because of her extraordinary oratory which poured through her like music, silver shot with gold, cataracting from summits of sheer inspiration. (Quoted in Izzat Yar Khan 1983, 17)
Makarand R. Paranjape, Making India: Colonialism, National Culture, and the Afterlife of Indian English Authority. Sophia Studies in Cross-Cultural Philosophy of Traditions and Cultures 2. Dordrecht: Springer, 2013. Page 187
Naidu was indeed a gifted orator, and gained her stature in Indian public life largely through her speeches. Her poems remain widely anthologized in Indian textbooks, because her native cultural references and premodern poetic idiom make them very approachable and an excellent teaching tool. As a result, she is remembered as a poet as well as a freedom fighter. But in her own day, her very public role as the most prominent woman in the independence movement long outlasted her vocation as a poet. Ranjana Sidhanta Ash writes:
As one of India's finest public speakers in English and occasionally in Persianised Urdu, Sarojini Naidu's career as an orator has yet to be reviewed as an aspect of her creative use of English rhetoric. ... She made frequent use of parallelisms by synonym, outright antithesis, repetition, alliteration, and crescendo. Skilled in delivery, with a superb sense of timing and abundant humor, she was as resourceful in her public debates as in her poetry; her verbal flow carried her audience along even when she was not clear in her argument.
Ranjana Sidhanta Ash. "Two Early-Twentieth-Century Women Writers: Cornelia Sorabji and Sarojini Naidu." Pages 126–134 in A History of Indian Literature in English. Ed. Arvind Krishna Mehrotra. New York: Columbia UP, 2003. p. 134.
My quoting Paranjape quoting Khan quoting Chattopadhyay above is a fine illustration of the vanishing origins of this phrase: all we have is its being quoted at multiple hands. And so we do not know whether the term "Nightingale of India" originated with Gandhi; nor whether it was originally an English phrase or a (mis)translated one; nor, if a translation, whether from Hindi or Urdu or Marathi; nor which bird is specifically meant; nor whether it referred to Naidu's poetry, her oratory, or both. And among all this uncertainty, one realizes also (as CDR has mentioned) that Naidu is not the only person to whom the phrase has been applied. Both Lata Mangeshkar and M S Subbulakshmi were also referred to as the nightingale of India. Amusingly, the Wikipedia article on Subbulakshmi claims, without any citation, that it was Naidu herself who referred to Subbulakshmi as "the nightingale of India".
Given its multiple possible origins and referents, the phrase "Nightingale of India" is aporiatic. It's also problematic in another way: it replicates imperialist gestures. Referring to an Indian poet (or orator, or singer) as a European songbird recasts the marginalized as an imitation of the metropolitan. The European terms of reference ("nightingale") are assumed to be universal, the Indian ("koel" or "bulbul") made meaningful with reference to those terms. The phrase also reinscribes hegemonic structures that associate the west with culture and the east with nature. If Naidu (or Mangeshkar, or Subbulakshmi) is a "nightingale", her art is cast as mere warbling, the instinctive performance of a noble savage, rather than being an expressive achievement or the result of aesthetic endeavor.
It's probably for the best, then, that we don't and can't know who was the first to refer to Naidu as the nightingale of India. It seems more imperative to be the last.
