tl;dr: The clone troopers did not overthrow Palpatine because they did not think he was acting against the interests of the Republic and they were not given orders to do so.
There are two meaning of the word "republic". For clarity, I'm going to use capital-R Republic to refer to the alliance of thousands of planets in the galaxy, and lower-case-r republic to refer to the system of government.
The clone troopers were loyal to the Republic, but not the republican form of government. When the name and form of government changed, it was still the same alliance of planets, and the clone troopers remained loyal to it. If the clone troopers did have an opinion on the change, I would guess that they would be in favor of it, as many others in the galaxy were (liberty dies with thunderous applause). The GAR system of operation was authoritarian, as all militaries are, and it would have seemed perfectly natural to them for civilian government to be the same, as that was all they had known.
Even if the clones did feel that Palpatine was acting against the interests of the Republic, they would probably not have removed him from office. They removed the Jedi only because they were ordered to by the Supreme Chancellor. If the Jedi had acted against the interests of the Republic, but Palpatine had not ordered their removal, they would not have been killed. Removal of the Chancellor would have required similar orders. Order 65, also given in True Colors, states:
In the event of either (i) a majority in the Senate declaring the Supreme Commander (Chancellor) to be unfit to issue orders, or (ii) the Security Council declaring him to be unfit to issue orders, and an authenticated order being received by the GAR, commanders shall be authorized to detain the Supreme Commander, with lethal force if necessary, and command of the GAR shall fall to the acting Chancellor until a successor is appointed or alternative authority identified as outlined in Section 6 (iv).
By this wording, the clones have no decision to make involving the Supreme Chancellor. He is to be removed if and only if the Senate or the Security Council gave the order. Obviously, no such order was given.
A final note on the phrase "new command structure". This is referring to the military chain of command, not the civilian government. Many of the Jedi served as generals or other commanders in the GAR, and they would need to be replaced. Whether the government is a republic or empire has nothing to do with it.