My guess is that your original heat sink was affixed with a "thermal pad" which is a bit harder than paste to remove. The gray substance should come off with isoprophyl alcohol. May take some soaking and rubbing with a plastic scrubber (aka "Dobbie Pad"). The purpose of thermal paste is to aid in the transmission of heat from the CPU surface to the heat sink primarily through the elimination of the air boundary layer between the two.
NOTE: Some thermal pastes (i.e AS5) have curing issues whereby they will not reach their full potential until after 200 hours of "thermal cycling". Some reviewers have estimated that this can the best pastes stake up to a year "under normal usage". Shint Etsu provides them best of both worlds as it matches the best of the best in ultimate performance but does so the same day you put it on.http://www.newegg.com/Product/Product.aspx?Item=N82E16835150080