After looking into this story a bit, I am leaning toward its being made up.
My strongest reason for doubting it is that I can't find any other evidence that MLK was a fan of Star Trek. If, as Nichols said, he not only liked the show but felt that it was a crucial step forward in civil rights, then you would expect him to say so more than once. It doesn't make sense that he would urge Nichols to stay on the show—and succeed, leading to the production of a whole second season of episodes with her in them (all of which were broadcast before his death)—only to never mention the show again. But as far as I can tell, he didn't. In Wikiquote's large collection of MLK quotes, and the associated talk page which contains conversations dating back to 2006, the words "Trek" and "Uhura" don't appear, and "Nichols" appears only in a quote by her about him. The Autobiography of Martin Luther King, Jr. and Let the Trumpet Sound: The Life of Martin Luther King, Jr. don't mention Star Trek, Nichols, or Uhura in their indexes. A Google search for his name and Star Trek turned up nothing that didn't trace back to Nichols's story.
I also can't find evidence that Gene Roddenberry told his part of the story. As related by Nichols in her autobiography Beyond Uhura, p. 165:
When I returned to work on Monday, I went to Gene's office first thing and told him about my conversation with Dr. King and my decision to stay.
A tear came to Gene's eye, and he said, "God bless that man. At least someone sees what I'm trying to achieve."
This seems like a story that Roddenberry would love to tell—praise from MLK would be a feather in his cap—but he doesn't seem to have told it. MLK isn't mentioned in Star Trek Creator: The Authorized Biography of Gene Roddenberry.
My remaining reasons are weak, but I'll list them anyway.
The conversation wasn't private: it took place at a fundraiser at which Nichols was a celebrity guest (according to a 2010 interview), and MLK was superfamous in any case, and they were introduced by a third party. I'd expect the conversation to have been overheard and perhaps independently reported on. I'd also expect them to pose for a photo together at some point, but no photo of the two seems to exist.
At least one story detail has been inconsistent. In her autobiography she planned to leave the show because of "the cuts and the racism", while in the 2010 interview she planned to leave the show because she'd been offered a role in a Broadway-bound play, and musical theater was her first love. In both tellings it seems to be her only reason.
In favor of the story being true there are the unpleasant implications of Nichols making it up, and the tweet by Bernice King that was mentioned in Laurel's answer. I have nothing intelligent to say about the first one. As for the tweet, it looks to me as though she learned about the story in the same way as everyone else, by reading an article that retells Nichols's version. At least, I don't see anything to suggest otherwise.
The article linked in the question also says that MLK and Nichols were friends (and "remained friends until he died"). Their source for that isn't clear. As far as I can tell, it isn't true and Nichols never claimed it was. MLK is only mentioned once in her autobiography, and they definitely weren't friends at that time (she was starstruck on meeting him).