Looks like much of it is dust, try rinsing very well (maybe washing it with some washing aid?) and hang up again.
Some dust may be dried into the emulsion though, so they may be stuck in there.
As for removing, i always use the patch/healing tool in Photoshop, (gimp equivalent tutorial here http://www.youtube.com/watch?v=VeNstnmXRgw ) , it's a much better tool than clone, because it samples from nearby areas and blends better.
Too bad you are not using Photoshop, I made an action for removing large amounts of dust when I used contaminated fixer once, was just too much crap on the negatives to sit and do manual removal, worked pretty well.