Holders Nigeria were handed a shock defeat at the start of the group phase of African Nations Cup qualifying on Saturday while Ghana also still seemed to be nursing a World Cup hangover.
Fellow 2014 World Cup combatants Algeria, Cameroon and Ivory Coast were in a happier mood after opening the campaign for a place at the Nations Cup finals in Morocco in January with victories.
There were also home wins for Burkina Faso, Gabon and Tunisia and an away triumph for the tiny Cape Verde Islands.
Zambia, winners in 2012, were held to a goalless draw at home by Mozambique.
Congo became the first country in 33 years to win a competitive match in Nigeria as they beat the Nations Cup champions 3-2 in Calabar with two goals from French-born striker Thievy Bifouma.
Nigeria were last beaten in a competitive home game when they lost 2-0 to Algeria in a World Cup qualifier in Lagos in 1981.
With a possible ban from world soccer's ruling body FIFA hanging over them for government interference in football federation matters, they were caught out in their opening Group A game on Saturday.
Efe Ambrose headed the hosts in front after 13 minutes but Congo captain Prince Oniangue equalised three minutes later.
Bifouma, who had a brief spell on loan at English Premier League West Bromwich Albion last season, put Congo 2-1 ahead in the 40th minute before he converted a penalty in the 54th.
Congo had been eliminated in the early knockout rounds but were given a reprieve when opponents Rwanda were found guilty of fielding an ineligible player.
Ghana needed a penalty and a post to avoid defeat at home to Uganda in Kumasi, drawing 1-1 in Group E.
FRESH START
The Black Stars were looking for a fresh start following their World Cup woes which included a strike by the players over money and the sending home of Kevin-Prince Boateng and Sulley Muntari for indiscipline.
Ghana had to come from behind after a long-range effort on the turn from Tony Mawejje gave Uganda a surprise lead on the stroke of halftime.
The hosts were awarded a penalty when Denis Iguma fouled Abdul Majeed Waris in the 50th minute and Dede Ayew converted the spot kick.
Ghana were then grateful to see Luwagga Kizito's angled effort come back off the upright in the second half.
Cameroon put a desperate World Cup behind them as debutant Clinton Njie and striker Vincent Aboubakar scored in a 2-0 victory in the Democratic Republic of Congo.
Stephane Mbia produced a captain's performance at left back having taken the armband from Samuel Eto'o who announced his international retirement last month.
Ivory Coast began a new era without Didier Drogba, who has also quit the international stage, by defeating Sierra Leone 2-1 in the other Group D game.
Gervinho scored the winner as the Ivorians came from behind to beat their west African rivals.
Sierra Leone were severely affected by the Ebola virus outbreak in the leadup to the game, with support staff prohibited from travelling to Abidjan by Ivorian health authorities.
In Group B, Algeria won 2-1 at Ethiopia while heavy rain meant the match between Mali and Malawi was called off.
Yacine Chikaoui scored a late penalty to give Tunisia a come-from-behind 2-1 win over Botswana while Samson Mbingui netted with a scorching shot as Gabon beat Angola 1-0.
Burkina Faso, runners-up at the last finals, overcame Lesotho 2-0 with goals from Jonathan Pitroipa and Alain Traore while Cape Verde scored three times in the first 24 minutes to win 3-1 in Niger.
Click here to watch the full highlights of the match between Ghana vrs Uganda