Restating calls for a general election, Mr Cameron said Mr Brown did not have a mandate to rule and two years after becoming PM was in "deep trouble".
Cabinet ministers dismissed calls on Wednesday by two Labour veterans for a secret ballot on Mr Brown's leadership. Lord Mandelson told the BBC Mr Brown's future as Labour leader was secure.
In an interview with BBC Radio 4's Today programme Mr Cameron said it showed the government was "deeply divided" at a time when Britain needed leadership on issues like Afghanistan and Britain's budget deficit.
He said if stories suggesting that Mr Brown does not have the support of senior colleagues were true "people will ask why should anyone else support him? If ever there was a time when our country needed strong leadership and united government it is today. We've got this massive budget deficit, we are at war in Afghanistan we've got deep social problems and yet we've got a government completely divided."
"We cannot go on like this, we've got to have an election and a change of government."
He said Mr Brown - who succeeded Tony Blair as prime minister in 2007 when he was elected party leader by Labour MPs - did "not have either a clear mandate from his party" or from the country. Mr Brown was eventually the only candidate in the leadership race as bids by left-wing Labour MPs to oppose him failed to gather sufficient support.
And Mr Cameron said, unlike other prime ministers who have faced challengers to their leadership, like Margaret Thatcher, John Major and Tony Blair: "Gordon Brown has only been prime minister for a couple of years and is in deep trouble with a deeply divided party."
He said leaders had to know "when the right time to step off the stage is".
Former defence secretary and chief whip Geoff Hoon and former health secretary Patricia Hewitt sent a letter to all Labour MPs on Wednesday, saying Labour was divided over Mr Brown's leadership. They said a secret ballot was the best way to resolve these differences and unite the party ahead of the general election campaign - but were publicly supported by only a handful of backbench MPs.
Cabinet ministers came out against the idea of a ballot and by the end of the day it appeared there was little momentum behind the idea. Mr Hoon later told the BBC that "by and large", MPs "had not taken" the opportunity of confronting the issue of the leadership.
But the BBC has learnt plotters against Mr Brown felt six Cabinet ministers may back them in the "right circumstances". Labour MP Eric Joyce suggested Mr Hoon and Mrs Hewitt had been encouraged by a few senior Labour figures. He added: "I think it's fairly widely known that there are a few people who imagine, if they just sit there quietly, the backbenchers will deal with the work for them and they can perhaps inherit for a brief period the prime ministership. That has now passed."
Business Secretary Lord Mandelson, a key ally of Mr Brown, told BBC 2's Newsnight the revolt had "blown through the corridors of Westminster and out of the window. The party has reached a settled view. They want Gordon Brown to lead the party as prime minister into the general election whenever it takes place and they don't want to open the question of the leadership."
Given that the deadline for calling the next election is June, and the vast majority are called in May, Cameron's got to know that the elections aren't going to happen now. It sounds like he's trying to paint himself as this great crusader against a dithering government, when in reality everyone knows that what he's asking for just won't happen. It could, theoretically, but it won't.