which provoked the "Super Caley go ballistic, Celtic are atrocious" headline in The Scottish Sun and resulted in the sacking of John Barnes. Dalglish took over as manager until the end of the season, during which time Tébily appeared irregularly. In the 2000–01 season, new manager Martin O'Neill gave him only three first-team starts. He began the next season in the first team and playing well, but lost his place once Bobo Baldé regained fitness. He still made enough appearances to qualify for an SPL winners' medal and received an unlikely nomination for the 2001 African Footballer of the Year award. Tébily wanted to play regularly, which was not going to happen at Celtic, so it was considered best for all parties if he was made available for transfer. On 22 March 2002, he resumed his association with manager Steve Bruce when he moved to Birmingham City, then playing in the Championship, for a fee of £700,000. Celtic clearly thought he had potential for improvement, as they had a sell-on clause included in the deal. He had scored twice during his spell at Celtic, once in a UEFA Cup tie with Cwmbran Town and another in the 8–0 thrashing of Stirling Albion in the League Cup. Birmingham City Bruce had taken over at Birmingham some three months previously and was in the process of rebuilding the team with a view to reaching the play-offs. He saw Tébily's major attributes as his size, strength and pace; a quality which soon became apparent was his whole-hearted commitment to the cause, as exemplified by his performance in the play-off semifinal against Millwall. Playing in an unaccustomed central midfield position, he man-marked Tim Cahill, later of Everton and Australia, out of the game, and won the ball from Stuart Nethercott with a full-blooded tackle having earlier lost his boot. In that season, Tébily never finished on the losing side at club level, either for Celtic or for Birmingham. Tébily played regularly in Birmingham's first Premier League season until 21 December, when he damaged his medial knee ligaments in the first 20 minutes of the match against Charlton Athletic. In keeping with his "hard-man" image, he finished the game, but the injury proved serious enough to keep him out for the rest of the season. Returning fit at the start of the 2003–04 Premier League season, Tébily found himself no longer first choice, though his