A nominally multiparty system was not necessarily incompatible with Communist rule. The east European "peoples' democracies" were mostly not (theoretically) one-party states. The typical pattern was this: in addition to the Communist (or "Workers") party, there were other parties which were tolerated as long as they accepted the "leading role" of the Communists. They were not competitive or rival parties, although they often had their roots in--or at least took the names of--bona fide historical parties. Rather, their purpose was to convince non-proletarian (peasants, petty bourgeois) or non-Marxist (Christian) elements of society to accept the Communist-dominated regime. Examples were the Christian Democratic, Liberal Democratic, Farmers, and National Democratic parties in the GDR; the Agrarians in Bulgaria, the Socialist party (basically those people from Benes' old National Socialist Party who went along with the Communist take-over in 1948) in Czechoslovakia, the United Peasants Party in Poland, etc. Typically, all parties would run candidates for the National Assembly on a single slate (the "National Unity Front", "Fatherland Front", etc.) which was of course dominated by the Communists and was unopposed and would get at least 99% of the vote in the "elections." A similar pattern existed (and still exists) in China:
http://en.wikipedia.org/wiki/List_of_political_parties_in_the_People's_Republic_of_China
(One party which was *not* allowed was the Social Democrats--because like the Communists they claimed to be Marxist and to represent the working class. Obviously, such claims could not be allowed, so one of the key measures in consolidating Communist rule in the late 1940s was the forced "merger" of the Communists and Social Democrats into unified "Workers" parties, which were really little more than the Communist Party under a new name. The merger process was facilitated by the fact that some of the "Social Democratic" leaders like Zdenek Fierlinger in Czechoslovakia were basically Communist "moles.")
One interesting (to me, anyway) detail is that in the PRC the nominally multiparty system is the result of Stalin, who overruled Mao's suggestion that a one-party system be established following victory. See Stalin's telegram of April 20, 1948: "We are very grateful for the information from Comrade Mao Zedong. We agree with the assessment of the situation given by Comrade Mao Zedong. We have doubts only about one point in the letter, where it is said that “In the period of the final victory of the Chinese Revolution, following the example of the USSR and Yugoslavia, all political parties except the CCP should leave the political scene, which will significantly strengthen the Chinese Revolution.” We do not agree with this. We think that the various opposition parties in China which are representing the middle strata of the Chinese population and are opposing the Guomindang clique will exist for a long time. And the CCP will have to involve them in cooperation against the Chinese reactionary forces and imperialist powers, while keeping hegemony, i.e., the leading position, in its hands. It is possible that some representatives of these parties will have to be included into the Chinese people's democratic government and the government itself has to be proclaimed a coalition government in order to widen the basis of this government among the population and to isolate imperialists and their Guomindang agents. It is necessary to keep in mind that the Chinese government in its policy will be a national revolutionary-democratic government, not a communist one, after the victory of the People's Liberation Armies of China, at any rate in the period immediately after the victory, the length of which is difficult to define now. This means that nationalization of all land and abolition of private ownership of land, confiscation of the property of all industrial and trade bourgeoisie from petty to big, confiscation of property belonging not only to big landowners but to middle and small holders exploiting hired labor, will not be fulfilled for the present. These reforms have to wait for some time. It has to be said for your information that there are other parties in Yugoslavia besides the communists which form part of the People's Front."
http://digitalarchive.wilsoncenter.org/document/113618
But all these "non-Communist" parties were basically a concession to the "backwardness" of the People's Democracies--these countries had not yet fully built Socialism, the petty bourgeoisie remained, and it was advantageous to have parties that would facilitate its acceptance of the "leading role" of the Communist Party. Also, in some of these countries religious sentiment was more widespread than in the USSR, and parties like the Christian Democratic Union in the GDR were designed to facilitate Christian support for the regime and for the Soviet-bloc "peace"campaign. CDU members were even allowed to vote in the Volkskammer against the liberalization of abortion law--AFAIK the only case of non-unanimous voting in that body.
https://en.wikipedia.org/wiki/Christian_Democratic_Union_(East_Germany) (I read somewhere that East German poet Johannes Bobrowski.a member of the East German CDU, once described himself as a "non-Marxist who accepted the socialist structure and destiny of the GDR.") Soviet authors praised the minor parties in the People's Democracies but added that for the USSR itself to have any additional political parties would be a backwards step.
Incidentally, one possible reason Soviet soldiers stationed in the "peoples democracies" were forbidden to mix with the civilian population is not just that they would see that people were more prosperous there than in the USSR but that even in a hard-line country like the GDR the difference in political systems from that of the USSR might lead to unorthodoxy. Brian Moynihan wrote in
Claws of the Bear: The History of the Red Army from the Revolution to the Present(1989) "The extreme sensitivity even towards the most faithful satellite, East Germany, is revealing. A dissident in Moscow told the author, 'East Germany has more than one political party. That may mean nothing to you, since the SED is totally dominant. But to us it means plurality and a sort of freedom. The army doesn't want any soldier stumbling on to that kind of idea.'" (p. 451)