Telephone-based sampling is hardly random sampling, given that most people don't answer calls they don't recognize the caller ID for. Those who do might be pre-disposed to certain sets of political ideology. What we may be seeing is a shift of people who are willing to answer the telephone and take a survey, not a net shift in political opinion.

A practical example, given in good faith: It may be that in their "random telephone sampling" they are only connecting with older people (who are usually more likely to answer calls from an unknown number), leading to unintentional selection bias. In this example, the confounding factor is age, and as such the gallop graphs could be simply showing that younger (ostensibly left-leaning) people are growing less willing to answer the phone (as opposed to the claim that Americans are moving right, idiologically)