В касавшихся Африки законах Юстиниана мы видим императора, у которого был план. Насколько этот план был реалистичен – другой вопрос. В конце концов, он был составлен по итогам неожиданно быстрой и (с точки зрения римлян) относительно бескровной победы. Решение Велизария вернуться в Константинополь вместе с Гелимером было отчасти продиктовано политическими соображениями, после того как офицеры из окружения военачальника стали обвинять его в планах захватить королевство себе. По словам Прокопия, Велизарий чувствовал необходимость лично поговорить с императором, чтобы восстановить свое честное имя. Вероятно, император тоже очень хотел поговорить с Велизарием. Однако отсутствие военачальника, подвергшего унижению вандалов, немедленно привело к возобновлению берберских набегов в регионе. Этой проблемой пришлось заняться новому преторианскому префекту Африки Соломону. Он атаковал большой лагерь берберов, расположенный к западу от Кайруана, и‚ по некоторым сообщениям‚ убил более 10 000 человек и взял в плен множество женщин и детей [74].

Однако агрессивные военные действия римлян в этом и других приграничных регионах империи одинаковым образом приводили лишь к более решительному и скоординированному ответу со стороны соперников и врагов империи, и в результате набеги берберов на Бизацену продолжались и становились все более серьезными. Соломон вновь атаковал лагеря врага, обложив крупное поселение на склонах горы Бургаон. Считается, что число жертв среди берберов составило около 50 000 человек, а в рабство угнали стольких, что, по словам Прокопия, берберского мальчика можно было купить по цене овцы [75]. Кому бы ни «возвращали свободу» в Африке после этого завоевания, это явно были не берберы.

Конечно, не все группы берберов выступили против римлян после отбытия Велизария в Константинополь, но их реакция была разной. Главный военачальник в окрестностях Бизацены, грозный Антал, в целом остался союзником римлян. Предводитель берберов в Нумидии, воин по имени Иуда, был определенно враждебен и регулярно совершал набеги на оседлые общины. Оба предложили убежище тем, кто выжил в устроенных римлянами бойнях. В 536 году Соломон решил повести свои силы к опорному пункту Иуды в горах Орес, но ему помешало растущее недовольство в рядах его собственных войск. Превращение армии завоевателей в армию оккупантов никогда не бывало легким, особенно притом, что многие воины в этой армии фактически являлись иностранными наемниками, призванными или нанятыми для особой цели. Ближе к Пасхе 536 года разразился крупный мятеж, возглавленный герульским военачальником Стотцей, которого с воодушевлением поддержали войска варваров арианской веры. Их не устраивало, что им запрещают соблюдать христианские обряды как они считают нужным; кроме того, они считали, что им положены военные земельные наделы, которыми раньше владели рядовые вандальской армии и которые Соломон и его чиновники быстро переводили во владение империи [76].

Есть все признаки того, что Стотца собирался объявить себя королем преобразованного африканского королевства [77]. Разумеется, Соломону пришлось бежать из Карфагена, и город чуть было не сдался мятежникам, разбившим лагерь у городских стен, но тут морем внезапно вернулся Велизарий и быстро принялся укреплять и покупать поддержку римского войска. В успешном бою он сумел прогнать врагов от стен города, а оставшиеся мятежники бежали вместе со своим предводителем в Нумидию. По причинам, которые вскоре станут ясны, Велизарию вскоре пришлось отправиться на Сицилию, и Юстиниан послал в Африку Германа, своего двоюродного брата (еще одного племянника Юстина), чтобы тот помог восстановить порядок. Когда Герман наконец прибыл, чтобы подавить бунт, он обнаружил, что примерно две трети оставшегося войска перешли на сторону восставших. Росло недовольство по поводу задержки в выплатах жалованья [78]. Возвращение контроля над ситуацией потребует большого рвения и крупных денежных сумм – и то и другое было трудно получить при дворе Юстиниана. Вандалы были побеждены, но борьба за Африку была далека от завершения. Но почему же Велизарий поспешил на Сицилию, когда он явно все еще был нужен в Карфагене? Причина крылась в том, что армия Юстиниана теперь вступила в новую и еще более амбициозную войну по возвращению территорий.