Most likely the corrosion is down in the cable and impossible to get cleaned 100%.

The procedure for replacing the starter cable would be to disconnect the negative terminal battery cable. Now that it'* disconnected you are safe as long as it doesn't touch the connection for the negative.

Remove the bolt for the positive side cables. Determine that the cable you are replacing runs down and toward the driver side of the car. Following that cable through a wire loom to the starter where it is held to the starter with a 13mm nut. If your car has a splash shield this is the point where you start swearing at it. Jack and support the car enough to get under it. Remove the #@$%#$^#$% shield if you have one. Disconnect the cable from the starter with your 13mm wrench or socket and ratchet. Connect the new cable to the same location, using a small screwdriver, open the wire loom holding clips and remove the old wire while adding the new one. Connect to the battery along with the other cable. Then reconnect the negative cable. Back in business.

Thanks for the great instructions, I'm pretty sure I got it now! But just to make sure, before I do it... on the pictures above, you'll see the metal part on the battery end of the cable is different from the ones I have.... it'* thicker and smaller in diameter. Will it still work? Or should I stamp my feet and pout because I have to go back to autozone....

It'* a (crappy) universal cable that can be made to work if the bolt fits through it.