You're exaggerating. They had to be tolerant of the Orthodox church because it was the only institution large enough and respected enough to possibly have the critical mass to rouse the population to rebel. But they weren't so tolerant of other branches of Christianity, much less other branches of Abrahamism (except maybe in the southern Turkic/Mongol/Persian republics where Islam had the same status as Orthodoxy in the north). Non-Abrahamic faiths were handled on a case-by-case basis. The poor Jews thought they were going to get a break when the Czar was overthrown, so many of them happily joined the Party. But it appears to be their destiny to never get a break--except in our country. Sure, the communist government was not as monolithic as we think, and there were certainly churches, synagogues and other places of non-Orthodox worship scattered across the country. But on the balance, most people who were not Orthodox, atheist, or simply kept their faith to themselves and talked to God at home, had to be wary.