Garang, a former southern rebel leader who was sworn in as vice president only on July 9, played a key role in reaching the peace deal earlier this year, ending 21 years of civil war that killed more than two million people.
State television had initially reported that air traffic controllers had lost contact with Garang’s aircraft on its way from Uganda before saying it had landed safe and sound "at a camp" in the south.
According to a senior Ugandan official, however, the Sudanese television report that Garang landed safely is incorrect and a search will continue Monday.
"The report that he landed at an army base in southern Sudan is wrong," the official told AFP on condition of anonymity.
Garang had been in Uganda to meet with Museveni.
The official said that Garang and his entourage left Museveni’s ranch in the western Ugandan town of Rwakitura in a Ugandan government helicopter on Saturday during daylight.
At some point during the flight they encountered bad weather and tried to go around it. Radio contact was then lost and it is unclear what happened to the helicopter.
"There was bad weather, they tried to go around it but may have crash-landed somewhere," the official said.
A source in Garang’s Sudan People’s Liberation Movement/Army (SPLM/A) told AFP that two Ugandan military helicopters had been sent to search for the missing aircraft shortly after contact was lost with it late Saturday.
"Yesterday evening the Ugandan government sent two military helicopters to search for them but they came back without any success," the source said.
In Nairobi, where the SPLM/A was largely based during the two-decade conflict, a spokesman told AFP that Garang had landed safely in southern Sudan. "These rumors are baseless. Garang is well and sound in southern Sudan, he arrived from Uganda (Saturday)," said SPLM/A spokesman Yasser Arman.
Earlier another spokesman for the group said the leadership was in a "crisis meeting" but had no word on Garang’s fate or that of the aircraft.
"We are in a crisis meeting, I cannot speak to you now," said Sampson Kwaje.
According to diplomatic sources in Nairobi, there had been rumors since early Sunday that Garang’s aircraft had crashed and that the ex-rebel leader may have been killed.
Diplomatic sources also said there was unconfirmed information that Garang’s helicopter crashed in Uganda’s northeastern Kidepo Valley, which is near the Sudanese border, and that all the occupants survived.