He alleged Fifa vice-president Jack Warner, Paraguayan Nicolas Leoz, Brazilian Ricardo Teixeira and Thai Worawi Makudi sought "bribes" in return for backing England's failed campaign.
Concacaf president Warner said he "laughed like hell" when he first learned of Triesman's allegations that he asked for around £2.5m to build an education centre in Trinidad.
Teixeira, the Brazilian football federation president, labelled Triesman's accusations as "absurd" and said he was considering legal action.
Nevertheless, Fifa said there was "extreme concern" at the latest allegations, with president Blatter pledging swift action.
Blatter, who is seeking re-election on 1 June, said his organisation must answer the latest round of allegations in three weeks.
"We have to deal with this matter before the congress and not just kick it out of the minds of Fifa," he told Al-Jazeera television.
"We have to do it now, immediately. We must accelerate the movement, whether it is for the good or for the bad."
Fifa has also asked for evidence from the Sunday Times after it made claims of bribery in the 2022 voting process.
A statement from Fifa said that secretary general Jerome Valcke had written to the newspaper seeking "any piece of evidence with regard to the statements made to MP John Whittingdale".
Collins calls for Fifa investigation
The MP for Maldon, Essex, is the chairman of the House of Commons culture, media and sport select committee where Triesman made his claims on Tuesday during a hearing about the country's failure to secure the right to host the 2018 World Cup finals.
Another member of the select committee, Conservative MP Damian Collins, said evidence submitted by the Sunday Times claimed Fifa executive committee members Issa Hayatou, from Cameroon, and Jacques Anouma, from the Ivory Coast, were paid nearly £1m to vote for Qatar's successful 2022 bid.
Hayatou, president of the Confederation of African Football (Caf), "categorically rejected" allegations of bribery in a statement on the Caf website on Wednesday, while Mohamed Bin Hammam, the Qatari president of the Asian football confederation who did much to secure the 2022 World Cup for his country, insisted Qatar had paid no bribes.
"I can assure you nothing like this has happened from our side," said Bin Hammam, who is challenging Blatter for the Fifa presidency.
"If someone wants to damage reputations like this then they have to provide the proof. You can't just accuse people just like that.
"It didn't happen. It is fine to say something, to try to damage the reputation of somebody but where is the proof?"
Fifa insist the voting process for the 2018 and 2022 World Cups was conducted cleanly.
But Chuck Blazer, a key player in the United States bid beaten by Qatar and a member of the Fifa executive committee, is keen to know more about the fresh claims.
"It's very sad to see all these allegations swirling around," he told the BBC. "We will have to wait and see what evidence is now submitted.
"My understanding is that these claims were not originally submitted by the newspaper. Let's see what they say. But if proved to be true I would have a lot to say on the matter.
"I hope they aren't true because I would not like to think the process went in that direction."
Australia, who also lost out to Qatar in the 2022 voting, has already played down suggestions it could ask for a re-vote.
"Ultimately, this is a question that needs to be directed to Fifa, the governing body," said Prime Minister Julia Gillard.
"We were very disappointed. We put in a bid which was impressive and we pursued that bid in an ethical and impressive way."
"The first thing is the allegations are brought to the attentions of Fifa and make sure that happens in concert with the FA," he said.
"We have to back that up with evidence and I would hope Fifa follow the example of the International Olympic Committee, who went through a similar process after Salt Lake City.
"There is nobody currently bidding for the 2018 Winter Olympics who doesn't believe their system is fair and transparent - Fifa needs to be in the same position."
In a subsequent interview with the Press Association, Robertson advised against canvassing support to re-stage the 2018 vote process.
England were knocked out in the first round with only two votes as Russia were awarded the tournament, while Qatar were named 2022 hosts.
"There is no practical chance of the process being re-run - that would be a huge admission of failure by Fifa," added Robertson.
"We have to be honest as a country that Lord Triesman made these allegations in Parliament but they are going to be very difficult to actually prove because these were just conversations he had with individuals."
Jacques Rogge, president of the IOC, said sports leaders must fight against corruption to prevent the type of scandal shaking Fifa.
Rogge said there was "always the threat" of unethical behaviour in sports management but stressed that claims made by Triesman and others on Tuesday must be backed "by solid proof".
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.