Attacks of Opportunity can't be replaced by immediate actions because they already are immediate actions. They're just really crappy immediate actions that aren't well integrated into the immediate action rules.
Look at them. They're a special action you can do outside of your normal turn, but only once per round. Sounds like an immediate action to me. Except they don't use up your immediate action, so you can use an attack of opportunity to respond to an opponent, then an immediate action to respond to your opponent again.
I don't mind if AoOs stay. But they need to be integrated into the rest of the rules. Give players one Immediate action per round. Make an Attack of Opportunity an immediate action that can only be used to counter your opponent's actions.
With iterative attacks going away and single attacks increasing in power, AoOs will get proportionally stronger since they're single attacks. The fact that they do more damage will make them more relevant on the battlefield, which makes them more palatable even if they slow gameplay. Meanwhile, the increase in mobility created by the loss of iterative attacks will make provoking AoOs more tempting.