As far as I can tell Krushchev was removed from office because of his erratic policies, and specifically their failures, but did his role in Stalin's purges also play a part in his removal?
From my understanding of Soviet history, it is unlikely that his role in Stalinist purges played any role in his removal. Few of the individuals who ran afoul of the Great Purges in the 1930's returned to political power (or an active social life/living life). At least not those who were implicated enough so as to hold a grudge. Additionally given the scope and chaos of the purges in the late 30's even a high ranking official like Krushchev had little control over the program and was himself a potential target. Krushchev ran a greater risk of offending the old Stalinist guard during his "secret speech" in the 20th congress denouncing Stalin.
Although, neither does the aforementioned speech or the Stalinist minority appear to be the motivation of the Brezhnev conspiracy. The conspirators were far more interested in furthering their political power for the sake of personal gain as opposed to an ideological objective, and neither the purges or Stalin seemed to play pivotal roles in their motivations. There is a good description of the heightened corruption of the nomenklatura in Moshe Lewin's "The Soviet Century" and it is a good general history of the Soviet Union, particularly in terms of political history.
This is completely irrelevant. The people who deposed Khrushchev were just as complicit as him. They might have held lower positions during the purges, but they were high enough to participate in them and benefit from them. If anything, they were angered by his "de-stalinization" efforts.
The main reason for Khrushchev's dismissal was that he started to ignore the other members of "Collective leadership" (e.g., by making extravagant gifts to China during his visit there without consulting with Moscow). This, together with the erratic nature of his policy, angered and scared his colleagues.
Here is a longer review of his failings and achievements (tl/dr crowd can stop here).
According to a popular joke, Khrushchev was deposed because of 5 "K":
Khrushchev promoted planting of Corn as a way to solve the chronic food shortages. As usual in the SU, this was taken to extremes (cf. destroying grapes during the Gorbachev sobriety campaign) and was only partially effective.
Cuban missile crisis was perceived as a defeat. Giving (albeit temporary) "control of weapons with an explosive force equal to 100 Hiroshima-sized bombs" to "mood swings and paranoia"-prone Castro was a bad idea.
Космос (Space Program)
The space program was enormously expensive. To sustain it, Khrushchev had to make many cuts in the other military programs (reduction of one-third in the size of Soviet armed forces, cancellation of some aircraft and artillery programs, abandonment of surface navy). This earned him widespread hatred in the military and defense industry.
First Khrushchev spent spent 7% of its national income between 1954 and 1959 on aid to China and returned Port Arthur and Dalian to China. However, the relationships cooled when China refused to toe the line and SU refused to allow China the liberty of having an own opinion.
Khrushchev promised Communism (non-monetary society) by 1980. This was widely viewed as unrealistic.
These achievement did nothing to endear him to the top brass, in fact, some consider them to be his failings
Хрущобы (Khrushchev + Slums)
For the first time in Soviet history something was done for the ordinary people. Yes, the houses were poor by modern standards, but these were the first houses built for the "population", not for "nomenklatura".
Not executing political opponents
Khrushchev started with executing Beria. The leaders of the Anti-Party Group were merely exiled (e.g., Molotov became an ambassador to Mongolia). A few months later Zhukov was only forced to retire.
This led to huge repercussions throughout the system: people realized that the "up (promotion) or out (execution)" system designed by Stalin was over. This led to a momentous change in functioning of the state/party apparatus - it became even less efficient and corrupt than it had been under Stalin.
The main motivation, both officially stated, and in my opinion also the real reason behind the dismissal of KHruschev was his poor performance. This included both economy and foreign policy.
Even today he is accounted as one of the weakest leaders according the polls. In foreign policy he lost good relations with China, in economics he allowed for inflation and the rise of consumer prices, he is also responsible for dramatic drop in the quality of the production, empathising quantity over quality, which manifested universally, even in architecture. The real estate of KHrushchev's era still remains the cheapest in the Russia's real estate market.