I've looked through the relevant code, and unless something breaks in the referendum process itself (which isn't impossible, but I think is unlikely), you will be able to reform the government.
Basically, the logic of the game says, "If you're ruler, and the government system is Anarchy, you can reform the government."
That particular bit of code doesn't care how you got to that point.
Sounds good.
Theocracy in t-minus 3...