The decision to move to a new electoral system was made in 1993. The first MMP election was meant to be in 1996, and there was a great deal of work to be done between 1993 and 1996 to prepare for that election. Electoral boundaries had to be redrawn. There was a complete revision of the chief electoral officer's processes and procedures, and the systems necessary to deliver it had to be designed and developed. There was a comprehensive electoral information campaign that needed to be developed.
The public officials who supported the cabinet processes, the executive processes, and the parliamentary processes also needed to review what difference coalition governments and a greater number of parties would make to the way cabinets worked and the way parliamentary processes worked. For example, there were amendments to standing orders of Parliament to make allowances for the new system.
Political parties also needed to adjust. There was a new nomination process that political parties needed to get their heads around. A new campaigning style was required, because the party vote became a very important feature of election campaigns. It was a new thing for political parties to understand.
All of those things required time.