The accusations of foreign involvement, reminiscent of a disastrous 1998-2002 war that drew in eight African nations, stoked fears of a wider conflict in this mineral-rich nation.
The fighting has forced tens of thousands of refugees to struggle through the countryside with what belongings they can carry. Tropical rainstorms, which drench eastern Congo every day, add to their misery.
On Tuesday, downpours sent refugees lucky enough to have shelter rushing to tents and huts made of woven banana leaves, while others huddled under plastic sheeting as they trudged through the thick red mud.
In Kibati, a camp for the displaced just north of Goma, aid workers from Los Angeles-based International Medical Corps gave water and high-energy biscuits to thousands of hungry children lined up in the searing heat.
Outside the distribution center, thousands of children who had not received the tokens needed to receive food shoved and pushed, holding their hands out in supplication, eyes wide with desperation.
"The people here don't have food and they are hungry," said Oxfam's Rebecca Wynn. "Some people are going into the banana fields around the camp, which is very dangerous because there are drunk soldiers around. They're risking their lives, but they are hungry and desperate."
Prime Minister Adolphe Muzito arrived in Goma just before dusk Tuesday with half his Cabinet and met with U.N. envoy Alan Doss and U.N. peacekeeping chief Alain Le Roy as well as local officials. He planned to meet with refugees Wednesday to assess the humanitarian crisis in the region.
Despite a week-old cease-fire, rebel leader Laurent Nkunda's Rwandan-backed rebels vowed insurgents would march on the capital, Kinshasa, after the government refused Nkunda's demand for direct talks.
"If they won't negotiate with us, then they leave us little choice," rebel spokesman Bertrand Bisimwa said. "We will start fighting again and we will continue until we take Kinshasa."
Communications Minister Lambert Mende said President Joseph Kabila's administration was "open for dialogue" with all rebel and militia groups in the region - but would not meet Nkunda's group alone.
The Congo government's first priority is to "normalize our relations with all our neighbors, above all Rwanda," Mende added.
Suggestions that other African nations are being drawn into the conflict have fueled fears of a wider conflict, adding urgency to U.N. Secretary-General Ban Ki-moon's attempts to bring Kabila and Rwandan President Paul Kagame together for talks. Kagame is believed to wield strong influence over the Tutsi-led rebels.
A U.N. official said Ban was considering leaving Wednesday for an expected African Union summit meeting Thursday on the Congo crisis in Nairobi, Kenya, to be attended by Kagame and Kabila. The official spoke on condition of anonymity because no official announcement has been made.
The rebels on Tuesday accused close Congo ally Angola and Zimbabwe of mobilizing to back government forces against the Tutsi fighters, while the government - backed by reports from U.N. peacekeepers - has said Rwanda is helping the insurgents.
The groundwork "is being laid for a generalized war in the region ... foreign troops (are) preparing to make war against us," rebel spokesman Bisimwa told The Associated Press.
Zimbabwe has strongly denied any military involvement, while Angola did not comment.
The conflict in eastern Congo can be traced to festering ethnic hatreds left over from the 1994 Rwandan genocide that killed a half-million Tutsis and sent more than a million refugees spilling across the border.
Rwanda invaded Congo twice in the 1990s to hunt down Hutu militiamen who fled there after taking part in the mass slaughter.
The 1998-2002 war ripped Congo into rival fiefdoms, with rebels backed by Uganda and Rwanda controlling vast swaths of territory rich in coffee, gold and tin. Angola and Zimbabwe sent tanks and fighter planes to back Congo's government in exchange for access to lucrative diamond and copper mines to the south and west.
Though Rwanda has denied any military involvement in the latest fighting, the U.N. says Uruguayan peacekeepers saw Rwandan artillery fire into Congo last week as Nkunda's forces advanced. Uruguayan army chief Gen. Jorge Rosales said intelligence reports indicated Rwandan troops were already "integrated in the rebel forces."
The rebels, meanwhile, claimed Tuesday that some Angolan troops were in Bukavu, south of Goma. They said 550 Angolan commandos were in Goma and others were in the central city of Kisangani. It was impossible to verify the claims.
Further complicating matters were the nearly two dozen small militia groups operating in Congo's lawless east, which the government and U.N. peacekeepers have struggled to secure for years.
Fighting erupted Tuesday between one of these, the pro-government Mai Mai, and the rebels north of Goma, U.N. spokeswoman Sylvie van den Wildenberg said. Uruguayan and Indian peacekeepers were caught in the crossfire at Kiwanja, but there were no reports of casualties.
At the International Criminal Court in the Netherlands, meanwhile, prosecutor Luis Moreno-Ocampo said Tuesday he was monitoring reports of war crimes in the Congo, including murders, rapes, attacks on civilians and looting. The perpetrators "will not go unpunished," he said.
Ross Mountain, the U.N. humanitarian envoy to Congo, told the AP the U.N. mission has pulled peacekeepers out of other trouble spots in Congo and has concentrated 92 percent of its 17,000-force in the east.
But at only one peacekeeper for every 10,000 civilians, the force was vastly unmanned, he said, noting that the Kosovo mission had 46,000 U.N. troops for an area 200 times smaller.
Neil Campbell of the Brussels-based independent think tank, International Crisis Group, said diplomatic efforts must be swift.
"The worst case scenario would be regional escalation with Rwanda getting heavily involved," Campbell said. "And that's something that we want to avoid at all costs."
In Kiwanja on Tuesday, AP reporters watched hundreds trudging home from refugee camps they said they were forced to leave by Nkunda's rebels.
U.N. spokeswoman Michele Montas said Nkunda's rebels blocked at least 100 refugee families attempting to return to Tongo, a village on the edge of the Virunga National Park that shelters endangered mountain guerrillas. Montas said the refugees were forced to sleep beside the road with no shelter.
Associated Press writers Michelle Faul reported from Goma and Todd Putman from Dakar, Senegal. AP writers Anita Powell in Goma, Eddy Isango in Kinshasa, Donna Bryson in Johannesburg, South Africa, and Louise Watt in London contributed to this report.