As Rwandan President Paul Kagame heads to Kampala on Sunday to meet Yoweri Museveni, all eyes will be on the two leaders to see how the resolve the simmering tensions.
The recall last week of President Museveni's advance team from neighbouring Rwanda has engulfed Kampala and Kigali in a cloud of speculation on the deteriorating relations between the two countries.
The Ugandan leader cancelled his planned trip to Kigali at the last minute for the signing of the African Continental Free Trade Area (AfCFTA) treaty despite the absence of pressing engagements back home.
This coming a few weeks after Rwandan president Paul Kagame missing a summit of the East African Community leaders in Kampala proving sufficient to feed the rumour mills in both capitals.
Presidents Museveni and Kagame share a deep historical bond, having fought alongside each other during the five-year bush war that saw the Museveni-led guerrilla force capture power in Uganda in 1986.
Despite this bond, the relations between the two countries have been characterised by mutual suspicion, and sometimes open deadly clashes.
Since Rwanda Patriotic Front (RPF) took power in 1994, Kampala and Kigali became strong allies, with security and strategic interests woven in the same ideology of military conquest, embedded in guerrilla wars that had deposed governments in Uganda, Rwanda and the DR Congo.
But during the Second Congo War (1998-2002) in which both countries -- driven mainly by the greed for Congolese minerals and timber, while strategic security interests were secondary -- were key players, Rwanda would wean itself of Uganda's patronising attitude, in the run-up to the infamous Kisangani clashes where both armies lost men in big numbers.
Kisangani accounts for the single biggest loss the Uganda People's Defence Force has suffered in its 37-year existence.
Survivors claim the Rwandans grew tired of orders from the UPDF over control of territory, and one day in 1999 they disobeyed and when the UPDF opened fire, the RPA retaliated. The armies were to clash again in June 2000.
Even without Mr Museveni, Uganda was one of the 44 countries to sign up on the AfCFTA through Foreign Affairs Minister Sam Kutesa.
But the near-muted and sometimes contradicting explanations from both Kampala and Kigali have failed to win over a sceptical citizenry who worry that relations between the two neighbours have hit an all-time low.
Sources say that Mr Museveni's advance team of security and protocol had arrived in Kigali on March 12, indicating that the president was set to travel to the Rwandan capital. President Museveni continued to preside over functions of his office, including flagging off the national netball team.
On March 21, the Daily Monitor reported that for a whole week, the Rwandan security agencies frustrated the efforts of Mr Museveni's advance team to establish the Ugandan leader's accommodation arrangements, the vehicles and routes he would use en route to the summit venue while in Kigali.
Officials in Kampala say that due to concerns arising from these frustrations, Mr Museveni's handlers ultimately advised that he skip the AfCFTA meeting.
But for months now, the relations between Kigali and Kampala have had a significant share of ups and downs, even prior to last week's events.
Last year, there were ripples in Uganda's security structure that included arrests of nearly a dozen senior police officers linked to alleged illegal arrests, kidnap and repatriation of Rwandan refugees -- who Kigali says are dissidents.
The police officers, who remain in detention as they answer their charges before the General Court Martial, signify a new low in the political tensions that beleaguer the two countries.
The sacking on March 3 of Inspector General of Police Edward Kale Kayihura and replacement by his deputy Okoth Ochola has also been linked to the tiff between Kampala and Kigali.
Albeit a first, the recall of Mr Museveni's advance party last week suits a pattern of events that have in the past seen the two countries' foreign policy, security and counterintelligence operations tested to the limit, to the point of seeking the intervention of third parties to help ease the tensions.
Shortly after, in 2001, Museveni would launch an international diplomatic war over Kigali. The Ugandan leader dragged Kagame before Claire Short, the former British Minister for Overseas Development, accusing Kigali of shielding and supporting Ugandan army officers Col Anthony Kyakabale and Samson Mande who had jumped bail in Kampala to start terrorist and armed and rebellion against his government.
Ms Short's mediation is said to have led to the two easing tensions, but tales by Foreign Service officials tell a different story.
Even in international fora, where world leaders gather, it is said that their body language remained stiff until 2011 when the relations softened somewhat.
Neither government has commented on the Museveni team's alleged mistreatment by Kigali.