طبيعة البربر في الانقسام وتخاذل الرؤساء نفست عليه قليلا اذ تطوع بعضهم لسليمان بالدلالة على طرق الوطن لتتبع بيداس. فخرج سليمان يطلبه حتى بلغ جبل اصبيديس (جبل شلية) ولكنه لم يظفر به ولم يبصره. وكان وقت الشتاء قريبا والمؤونة غير كافية للاقامة. فعاد الى قرطاجنة.
دخلت سنة (٣٦) وخرج فصل الشتاء. فتجهز سليمان في فصل الربيع لحرب بيداس. ولكن جنوده كانت قليلة الانقياد. فلما شق عليها تتبع هذا الامير في جباله شقت عصا الطاعة في وجه سليمان وعزمت على قتله، فما وسعه الا النجاة بنفسه. فأغذ السير الى قرطاجنة. ومنها ذهب الى صقلية- وبها بليسير - فأعمله بما جرى. فركب بليسير البحر الى قرطاجنة لاخضاع الجنود. وثارت بعده جنوده هنالك، فعاد سريعا الى صقلية. وبقيت افريقية الرومية بعده في فوضى عامة.
كانت تلك الجنود الثائرة بأفريقية متحدة تحت رئيس يدعى ستوزاس. وارسل يستنيان جرمان واليا. فحارب ستوزاس. وبينما هو فار أمامه الى ناحية بها بيداس وأرثياس طمعا في نصرتهما إذا بهذين الاميرين قد نزلا على جنوده واستأصلاها. ففر إلى موريطانيا. وكانت هذه المعركة بمكان يدعى "سلاص فاتاري" قال مرسيي: وهو اما نواحي تيفاش واما جنوب قسنطينة.
وفي سنة (٣٩) عزل جرمان وعين مكانه سليمان الخصي. فجعل حرب أوراس نصب عينيه. وكان على بربر البيزاصين أمير منهم يدعى اتتلاس. فاستماله سليمان وجعل له عطاء سنويا. وفي ربيع سنة (٤٠) أرسل أحد ضباطه لفتح أوراس. وخرج هو بأثره. ولما بصر هذا الضابط بالعدو لم يقف لحظة عن الفرار الى باغاية. فادركه البربر.