I think you should probably start with lower grit...
Start with say 200 or so, then 400, then 600, then 800, etc...
Bear in mind that the finer the sand paper, the less of the heatsink surface it removes (thus allowing you to get it closer to being completely flat). If there is a big gouge (big being relative, on the bottom of a heatsink a "gouge" can be quite small) you will only be able to practically remove it with a lower grade sand paper (it would take FOREVER with 1500 grit, for example). The idea is to get the larger imperfections out first and then finish sanding it smooth with the finer grits.