From memory, you replenish as soon as an upgrade is taken. Will see if I can confirm that in the rules...
EDIT: rules p7 says:
After a player has finished purchasing Upgrades, repopulate the empty slots on the Shop Board with new Upgrade Tiles.
So it's after a player has finished their upgrading.