بلغت صنهاجة من سعة السلطان وقوة النفوذ ما يحولها الاستقلال، ولكنها آثرت الارتباط بالعبيديين لئلا تشوش على نفسها داخليا وخارجيا، واشفق العبيديون من عظمة صنهاجة، فاخذوا يغرون بها كتامة التي تتمتع بوطنها لا يلي عليها صنهاجي ولا تنفر معهم في الحروب، وكانهم تركوا لها هذه الميزة لمثل هذه الدسائس.
ففي سنة ٣٧٧ ظهر بكتامة ابو فهم حسن بن نصر داعيا للثورة على صنهاجة، فكتب منصور بن بلقين الى العزيز بن المعز يستأذنه في قتال كتامة، فوجه له رسولين بالنهي عن ذلك، وأمرهما بالمسير الى كتامة بعد أداء الرسالة، فلما بلغ الرسولان المنصور نهي العزيز شعر بالمكيدة، فسجنهما وتأهب للحرب، فلما نزل على ميلة نشر البنود وقرع الطبول مزمعا على استئصال أهلها، فخرج اليه النساء والعجائز والاطفال بالتضرع، فرثى لمنظرهم حتى بكى، وابقى عليهم ونقلهم الى باغاية، وخرب سور ميلة، وسار نحو سطيف لا يمر بقصر او منزل الا هدمه، ووقع قتال شديد على سطيف، ثم انهزمت كتامة، وفر ابو فهم الى جبل وعر، فنزل على أهله بني ابراهيم من كتامة فلم يحموه، وقبض عليه منصور، فقتله، واقام نائبا بميلة وسطيف، ثم سرح الرسولين الى العزيز، فارسل له العزيز يطيب قلبه، واهدى له هدية جليلة، وسكت عن قضية ابي فهم.
وفي سنة ٧٩ ظهر بكتامة ايضا ابو الفرج منتسبا الى القائم بن المهدي فعظم امره أكثر من ابي فهم حتى انه ضرب السكة باسمه، وجرت بينه وبين نائب منصور بميلة وسطيف وقائع كثيرة، ثم خرج له منصور نفسه، فأسره ثم قتله. وشحن بلاد كتامة بالعساكر، وبث عماله فيها لتمهيدها وجباية خراجها، ودخلت ضمن الجزائر الصنهاجية ولم يجد العبيديون سبيلا لاضعاف صنهاجة غير انهم