As several people have mentioned, there's nothing in the rules to stop you from Cleaving off an AOO. I'm one of the people who don't like it though. To me, an AOO occurs when someone has dropped his guard in combat, but that shouldn't make anyone else more vulnerable to an attack.
I like to use the invisible dire lemming example to illustrate this. Let's say there are two fighters, A and B, facing each other in combat. B has Combat Reflexes and Great Cleave, and has true seeing cast on him. Someone (maybe an ally of B) suddenly releases a pack of invisible dire lemmings (like dire rats, but more suicidal) and they run behind B. As they do so, they provoke AOOs for movement from him. B gets several attacks on the dire lemmings because of Combat Reflexes, and he easily kills each with one blow and Cleaves into A. The dire lemmings don't distract A because he can't see them. As far as A is concerned, he's keeping a wary eye on B, and defending himself normally against him. However, B suddenly erupts into a flurry of motion, landing several solid blows on A.
Yes, it's a pretty contrived scenario, but I hope it serves to illustrate why I don't think Cleaving off an AOO should work.