As the question asks, were the Nazis just convinced the Soviets defended the Jewish religion? Did the average German believe the propaganda? Did the Soviets do anything to discredit that propaganda? Thank you for the answers.
They weren't convinced the Soviets defended the 'Jewish religion', because for the Nazis 'Jewishness' was an ethnic/racial quality, not a religious one. A non-practicing or converted Jew was just as bad as an Orthodox Jew in the National Socialist worldview (though they did often use stereotypical trappings of Orthodox Judaism in their anti-semitic propaganda).
As for Russia's history of anti-semitism, that is true, but the Bolshevik Revolution was very emphatically not anti-semitic. Anti-semitism and other forms of 'national chauvinism' were in fact criminalized in Soviet Russia. National minorities in general, including Jews, were overrepresented in the early Bolshevik party and its various apparatuses. The idea of 'Jewish communism' goes back to Marx at least, because he was a Jew, but it picked up a lot of steam among the anti-communist European right because of the solid number of Jews to be found in the ranks of the Bolsheviks (Trotsky, Kamenev, Zinoviev, and Sverdlov, were all Jewish to name a few at the very top of the new regime). The 'Judeo-Bolshevism' canard predates the Nazis and was more or less a staple of the far-right during the interbellum years.
In Mein Kampf, Hitler outlines his beliefs regarding the USSR, the Russians, and the Jews. He believed that the great mass of slavic Russians were a rather indolent, disorganized people of 'inferior worth' who were easily ruled by more capable races. The Nazis believed that Jews as a race were akin to an infection that wormed its way into 'healthy' people and nations and destroyed them from the inside out. This was what Hitler believed had happened in Russia. He thought that, under the Tsarist regime, a small 'core' of Germanic blood (the Tsars and the Russian nobility) had ruled the millions of Slavic Russians, but with the Bolshevik revolution, this Germanic ruling elite had been overthrown and replaced by a Jewish elite.
In short, the Nazis believed that millions of Russians were being ruled by a small minority of Jews, hence the common image in Nazi propaganda of hordes of subhuman 'asiatic' Russians being driven forward with a pistol at their backs by 'Jewish commissars'.
You will likely be interested in my older answer:
Minorities of all kinds were frequently over represented in Communist party leadership, especially the more educated minorities, though Jews were not as far as I have found particularly supportive of communist parties in terms of mass membership or voting (in places like interwar Poland where voting for Communist Parties was an option). However, disproportionate Jewish leadership frequently meant that Jews were particularly visible.
For more on anti-semitism, see my old post here:
You may also be interested in this (and many other) answers from /u/commiespaceinvader:
For Jews in the Soviet Union, you might interested in this (and many other) answers by /u/kieslowskifan: