Because he could have been fired at ANY time by the board of directors of Kodak. You know the board? the people appointed by the owners to protect their interest in the company.
Perez was never fired and so served at the pleasure of the board.
That does not mean "Perez did *exactly* what Kodak's board wanted from him", as you stated. They wanted success; he did not deliver.
The "owners" are shareholders, and some of them were getting increasingly unhappy with Perez. But boards have a strong degree of autonomy; shareholders trust them, and removing a board requires a concerted effort by a significant number of them. Most shareholders are not involved or interested to that degree. That is why boards are usually re-elected with near-unanimity.
In general:
Boards sometimes hang with questionable decisions, thinking they will work out. There are good reasons why they do.
They want to believe they made the right decision. They assume competence. They want to give the chance to succeed, and they know that will take some time. Short time total busts like Apotheker are uncommon. It usually takes quite a while to become unsatisfactory to the point of being fired.
Firing a CEO can have a deleterious effect on a company in itself, giving the appearance of a company in disarray and shaking the confidence of shareholders. That can make make a board slow to fire.
There is also the issue that they have to find a replacement, substantially better than the one they fired, who is willing to take the job. At Kodak, that was becoming more difficult as time went on.
For a board to fire means admitting they made a mistake. It calls into question the judgment, therefore the competence of the board. And many boards are dominated by the CEO to a surprising degree. Along with being CEO, Perez was Chairman of the Board.
It is seldom as simple as you present it.