Do they make a tool for removing the chips? It's hard to be gentle. I got them out, cleaned and reseated, but needed a drink afterwards... Unfortunately still no sprites.
I bought an IC removal tool just for my PP boards. On the first chip I tried to extract, the tool broke.

I just use a slim flathead screwdriver, lift one side a little, lift the other side a little, alternating until I get it out.
As far as cleaning the legs, I use a fine sandpaper to knock off the surface corrosion. I'm sure you could probably use contact cleaner as well.
If the chips trick didn't work, have you checked your voltages and made sure you're getting 5V at the board? I've heard that 5.1V is even better.