Eisenhower's Secretary of Agriculture, Ezra Taft Benson, implemented some "pro-market" reforms that were very unpopular with farmers. I don’t know the details but it likely involved slashing subsidies. Ironically, Benson may have also been the reason for Eisenhower's surge in Utah, as he was an LDS Apostle and the first Mormon ever appointed to the Cabinet.
Also, 1956 was the peak of the great 1950s drought on the Plains, so it’s only natural that Stevenson gained there and in the West. Like in 1988 amidst another big drought, South Dakota and Montana voted more Democratic than the nation at-large in 1956 – this despite Eisenhower winning Silver Bow County, which has never voted Republican since.