One idea that came to me prompted by Angel was what if the clones weren't created for the Republic recently but had been created a long time in the past to fight in some ancient war and were held in stasis in a forgotten location and discovered and reactivated. Like the Krell city in Forbidden Planet.
There could be an in universe myth that they would return when the galaxy needed them the most.
It would tie into the classic Star Wars notion of taking a mythic idea (the sleeping phantom warrior army) but with a space opera twist.
They would still be clones but their hidden fortress could have been discovered by the Kaminoans (that would turn them into a salvage team getting rich on what they found rather than a race of cloners).
Once activated the awakened clones start producing more and are preprogrammed to serve the Chancellor of the Republic (which is why they obey all his orders and the main reason that Palpatine came out of the shadows to become Chancellor).
The PT grew out of the back story of the OT.
One of the reasons the PT seems so hollow is it doesn't have that much of a back story of it's own to call upon.
The few mentions of the Sith wanting revenge on the Jedi for something added to a few ideas like this would project the story even further back.
It would also take the heat off the Jedi allowing the Republic to create a race of slaves if they already existed generations before.
It would require a redub of a lot of dialogue and a lot of editing around but it may make for a more interesting idea.