It wasn't a full reprogram, but the implanted suggestions did increase and crystallise over time, as Bester described. It was cumulative and subtle to the point where you couldn't tell when the "true" Garibaldi was fully submerged. Remember Bester said he could still feel the real Michael, buried and beating at the inside of his skull.
But all that does is cement my original point: the only people who opposed Sheridan were either brainwashed or mass-murderers. If Garibaldi didn't have any genuine misgivings about Sheridan's activities, then there was really
no one with any legitimacy standing up against Sheridan.
The show never really dared to ask if what Sheridan was doing was right. Clark was a tyrant and his Earthgov had gone off the rails. Did that really justify a military-led coup, especially one led by a contingent from a
de facto independent space station, and backed up by
Minbari of all people?
I would think any reasonable person sitting on the other side of that would be fucking terrified. Everything Clark warned them about was coming to pass--the big boogeyman from B5 was rolling in with his Minbari fleet to conquer Earth.