I think many people have problems with the implementation of the AoO rules, rather than the concept.
For example, look at the number of special cases where you don't get AoOs:
1. Your only movement is a 5-foot step.
2. You double move...this only prevents an AoO from leaving the square you started on.
3. An enemy has already used up its AoO...unless it has Combat Reflexes. However, it still can't hit the same creature twice.
...and so on.
Still, most people seem to eventually get used to them. I personally enjoy the extra level of strategy they add to combat.