In the new Central Bedfordshire unitary authority Labour did not win a single seat, with 54 going to the Conservatives and 11 to the Liberal Democrats.
BBC political editor Nick Robinson said Mr Purnell's resignation was the first direct challenge to Mr Brown from a cabinet minister, and a message to the rest of the Labour Party to make up their minds about Mr Brown's leadership.
He also said that, according to a Downing Street source, a reshuffle is likely as early as Friday morning.
Mr Purnell, who was one of the most prominent Blairites in Mr Brown's top team, is the third cabinet member in three days to say they are standing down.
He added: "I am therefore calling on you to stand aside to give our party a fighting chance of winning. As such I am resigning from government."
The BBC understands Mr Purnell only came to his decision to resign on Thursday but is said to have been frustrated for some time.
A Downing Street spokesman said: "The prime minister is disappointed by the resignation of James Purnell, of which he was informed shortly before 10pm."
He said Mr Brown's focus over coming days would be "restructuring the government on the big challenges facing the country for the future", tackling the global economic downturn, trust in Parliament and reforming public services.
"He will continue to give his undivided attention to addressing these great challenges facing our country and putting the interests of the British people first and foremost," he said.
Mr Purnell, a former adviser and a current friend of Tony Blair's, has acted with the ruthlessness of his mentor
Downing Street said Mr Brown was "disappointed" but would be getting on with the job but David Cameron said the government was "falling apart".
Mr Brown was set to reshuffle his team within days as he fights to hang on to his tenure as prime minister.
Mr Purnell's resignation comes as a BBC poll suggests fewer people consider the prime minister to be competent, decisive or tough than at any time in his leadership.
Only 29% of the 1,005 adults surveyed by ICM for the BBC thought that Gordon Brown was in touch with ordinary people.
In contrast, David Cameron received his most favourable scores since he became Conservative leader.
In his letter to Mr Brown, published in Friday's newspapers, Mr Purnell said he owed it to the Labour Party to "say what I believe no matter how hard that may be".
He said he was not seeking the leadership but wrote: "I now believe your continued leadership makes a Conservative victory more, not less likely. That would be disastrous for our country."
But Conservative leader Mr Cameron, repeating his call for an immediate general election, said: "In a deep recession and a political crisis we need a strong united government. Instead we have a government falling apart in front of our eyes."
Graham Allen, MP for Nottingham North, gave his backing to Mr Purnell.
He told Sky News he hoped Mr Brown would "take the honourable way out so that the party can progress with a leadership election".
Meanwhile, other cabinet ministers have been rallying round Mr Brown.
Mr Hutton said Mr Purnell was a "good friend" but added: "I think he has made the wrong decision because I firmly believe that Gordon Brown is the right man to lead our party and our country."
Northern Ireland Secretary Shaun Woodward also said he was "deeply disappointed" by Mr Purnell's decision and that he fully backed Mr Brown.
A source close to Justice Secretary Jack Straw said he was "very surprised and deeply saddened" by the news and "remained very supportive" of Mr Brown.
And the BBC understands Foreign Secretary David Miliband, who was touted as a possible challenger to Gordon Brown's leadership last year, does not intend to resign and had said he did not agree with Mr Purnell.
Other Labour figures have strongly criticised the decision - former London mayor Ken Livingstone said it was no surprise as Mr Purnell had been "the most ultra-Blairite of ministers".
"If you were going to get a knife in the back it's where you would have expected it from," he said.
Backbencher Peter Kilfoyle, one of the few Labour MPs not to back Mr Brown for the leadership in 2007, told the BBC: "I'm very dismayed by the attitude of people like Purnell and indeed Hazel Blears."
He said they had been "self serving" in backing Mr Brown for the leadership and the cabinet should back him now: "They have a wider responsibility than merely their personal careers. It's also about the future of the Labour Party, not just in government but in the country."
The news comes as the polls closed across the UK for the European elections and, in England, 27 county and seven unitary council elections.
Senior Labour backbencher Barry Sheerman told the BBC there should be a ballot of Labour MPs to see if Gordon Brown still has the confidence of the party.
He said: "This goes far beyond just a few people, this is a large number of us who are really unhappy about the present situation."
But Labour's leader in the Lords Baroness Royall defended Mr Brown's style of leadership on BBC One's Question Time.
The Tory leader used his Webcameron site to react to the resignation
She said: "We haven't got a media star, we have got a person who works damned hard and is taking us through the economic crisis."
There have been predictions Labour could be pushed into third or fourth place in the Euro elections behind the UK Independence Party (UKIP), following damaging revelations about expenses claims in the Daily Telegraph.
Mr Brown's much anticipated reshuffle was pre-empted earlier this week with the news that Jacqui Smith had asked to step down as home secretary.
She later said she believed Gordon Brown was the right person to lead the Labour Party but was stepping down for her family - who had been "at the forefront" of expenses allegations against her.
Then Hazel Blears announced on Wednesday that she would be stepping down as communities secretary.
In her resignation statement she did not pay the customary tribute to the prime minister, who weeks ago had described her own actions on expenses as "totally unacceptable".
Alistair Darling's position as chancellor is also thought to be vulnerable after questions about his expenses.
Amid a fevered atmosphere at Westminster - where the expenses saga has dominated the agenda during the election - two junior ministers Beverley Hughes and Tom Watson have also said they are to step down.
Some Labour backbench MPs say they are circulating a letter among MPs seeking support for a call on Mr Brown to go.
About 70 Labour MPs would be required to nominate a specific alternative candidate to trigger a leadership contest.
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.