К новым выборам главы республики в августе 2003 г. оппозиция Семенову стала интернациональной. Наряду с «бывшими семеновцами» с карачаевской стороны против генерала активно выступил менеджмент ОАО «Кавказцемент» — одного из сильнейших, бюджетообразующих предприятий Карачаево-Черкесии. Генеральным директором предприятия был Алий Каитов — молодой карачаевский бизнесмен. Под одной крышей с администрацией «Кавказцемента» в центре Черкесска в 2003 г. располагался и «мозговой центр» штаба главного соперника Семенова — главы Центрального банка Карачаево-Черкесии карачаевца Мустафы Батдыева (последний доводился Каитову тестем). Однако помимо части карачаевской элиты за Батдыева единодушно выступило черкесское национальное движение. Также сторонники Батдыева активно работали с русским электоратом, создавая под своей эгидой русские национальные организации и способствуя изданию антисеменовской газеты «Я — русич!». Таким образом была выстроена конструкция, способная привлечь электорат всех основных национальностей республики. Семенову это не удалось — и он проиграл Батдыеву во втором туре, хотя и с небольшим отрывом.
Мустафа Азрет-Алиевич Батдыев родился 24 декабря 1950 г. в Казахстане, где его семья находилась в депортации. Карачаевец. Родовое село — Эльтаркач У сть-Джегутинского района Карачаево-Черкесии. Происходит из бедной семьи, не имевшей влиятельных родственников. Учился в школе-интернате в Черкесске.
В 1978 г. окончил экономический факультет. МГУ, в 1981 г. — аспирантуру МГУ. Среди сокурсников — вице-премьер правительства РФ Александр Жуков, первый зам. председателя ЦБ РФ Алексей Улюкаев, президент. Российского союза промышленников и предпринимат елей Александр Шохин.
В 1981–1986 гг. работал главным экономистом в колхозе «Родина» Прикубанского района Карачаево-Черкесии. В 1986–1991 гг.
— инструктор, заместитель заведующего, заведующий социально-экономическим отделом Карачаево-Черкесского обкома КПСС. В 1992–1994 гг. — председатель Госкомимущества — заместитель председателя правительства Карачаево-Черкесии. В 1994–1997 гг. — заместитель председателя правительства Карачаево-Черкесии. В 1997–2003 гг. — председатель Национального банка Карачаево-Черкесии (республиканского отделения Центробанка РФ).
31 августа 2003 г. одержал победу во втором туре выборов главы Карачаево-Черкесии, набрав 48,36 % голосов. До выборов президента не был в республике публичной фигурой. По неофициальным данным, оппозиция Семенову — как карачаевская, так и черкесская — стала «присматриваться» к нему как к возможному кандидату на пост, главы Карачаево-Черкесии еще в 2002 г. Во время предвыборной кампании сторонники Батдыева делали акцент, на его связях в Москве.
Покинул пост, главы Карачаево-Черкесии 4 сентября 2008 г., по истечении полномочий.
При этом было бы ошибкой утверждать, что выборы 2003 г. вовсе не «пересекались» с национальными проблемами. Этнические моменты отсутствовали в предвыборной риторике, однако появились при обсуждении результатов выборов. Так, Семенов получил максимальную поддержку в населенном почти исключительно карачаевцами Малокарачаевском районе республики (можно предположить, что этому способствовал верный «оруженосец» генерала, секретарь Совбеза Борис Батчаев, выходец из данного района). Батдыев же наиболее высокого результата — более 80 % — во втором туре добился в Хабезском районе, где проживают черкесы (с незначительными анклавами ногайцев и абазин). Такой результат наблюдатели связывали с активнейшей поддержкой Батдыева со стороны черкесских лидеров. Это впоследствии не раз припоминали ему оппоненты, подчеркивая, что безоговорочной поддержки в целом по республике он не получил.