It was known fact Harry was a parselmouth. Moreover Malfoys could easily frame him for it. So why didn't such news appear in the paper?
Because Rita Skeeter didn't have access to Hogwarts and Harry at the time.
The fact that Harry was a Parseltongue was common knowledge around Hogwarts during Harry's second year. Harry speaking to the snake at the Dueling Club was a very public event (and I imagine that even those who weren't present at the time came to hear about it through gossip). There certainly would've been plenty of people (including Draco Malfoy) who would've been happy to give the Prophet a juicy story.
“All I saw,” said Ernie stubbornly, though he was trembling as he spoke, “was you speaking Parseltongue and chasing the snake toward Justin.”
(Chamber of Secrets, Chapter 11, The Dueling Club).
The papers didn't lack people who were willing to talk. What they lacked was a reporter with insider connections who had access to the necessary sources. There may have been other Prophet writers who might've been interested in the story but the only one we hear about is Rita Skeeter. As a sensationalist, she would definitely have been interested in the story.
The Prophet is not an entirely unbiased source of news, and sometimes displays an unfortunately sensationalist tendency best epitomised by star reporter Rita Skeeter.
(Pottermore, "The Daily Prophet").
We know that she was working for the Prophet during this period. She had been since at least the First Wizarding War:
Harry noticed a witch halfway up the rows of benches opposite. She had short blonde hair, was wearing magenta robes, and was sucking the end of an acid-green quill. It was, unmistakably, a younger Rita Skeeter.
(Goblet of Fire, Chapter 30, The Pensieve).
It's important to state that Skeeter only got access to Harry because of the Triwizard Tournament. We know that Dumbledore was not a great fan of her but Ludo Bagman seems to have taken it upon himself to invite her to Hogwarts in order to generate some publicity for the Tournament.
"This is Rita Skeeter,” he added, gesturing toward the witch in magenta robes. “She’s doing a small piece on the tournament for the Daily Prophet ...”
(Goblet of Fire, Chapter 18, The Weighing of the Wands).
As we know, Skeeter was less interested in covering the Tournament than she was in producing a huge, front-page cover story about Harry. Skeeter made use of her access to Harry at this point to do the story. She also started interviewing other students, but only people like Colin Creevey (who was hardly likely to say anything that cast Harry in a negative light).
But Rita Skeeter had gone even further than transforming his “er’s” into long, sickly sentences. She had interviewed other people about him too.
Harry has at last found love at Hogwarts. His close friend, Colin Creevey, says that Harry is rarely seen out of the company of one Hermione Granger, a stunningly pretty Muggle-born girl who, like Harry, is one of the top students in the school.
(Goblet of Fire, Chapter 19, The Hungarian Horntail).
At this point Skeeter doesn't break the Parseltongue story because she doesn't know about it and isn't interviewing anyone who'd be likely to tell her.
Her initial story on Harry must have sold well as she subsequently became desperate to interview Harry again. It was at this point that she started digging around Hogwarts more and more, using her disguise as an unregistered Animagus. The success of her earlier article probably motivated her to take more and more risks, including revealing her secret identity to several Slytherins. Once Harry stopped speaking to her she realised that she had to go to his enemies to get the gossip.
And of course this did eventually lead to the publication of the news that Harry was a Parseltongue.
The Daily Prophet, however, has unearthed worrying facts about Harry Potter that Albus Dumbledore, Headmaster of Hogwarts, has carefully concealed from the wizarding public.
“Potter can speak Parseltongue, ” reveals Draco Malfoy, a Hogwarts fourth year. “There were a lot of attacks on students a couple of years ago, and most people thought Potter was behind them after they saw him lose his temper at a dueling club and set a snake on another boy. It was all hushed up, though."
(Goblet of Fire, Chapter 31, The Third Task).
It all comes down to access. During Chamber of Secrets Skeeter and the Prophet didn't have access to Hogwarts. It was only the Triwizard Tournament that gave her grounds for entering the school. Even then, it seems to have been on Bagman's invitation, not Dumbledore's. She started by talking to Harry's friends. It was only in the second half of Harry's fourth year that she started talking to his enemies. That was when she first heard that Harry was a Parseltongue. And as soon as she got that news she went to print.