Ah, that's the other thing. What is the tape? If it's Ampex 456, that might itself be the problem.
Might be a good idea to look at getting a fresh reel of RMGI SM911 or similar.
As for cleaning the heads, try to get some isopropyl alcohol, at least 90% pure. (Rubbing alcohol has too much water in it). To actually do the cleaning, I use cotton buds, other people prefer makeup pads or some other kind of swab. Basically you dip the cotton bud in the alcohol and scrub the head with it for a bit, preferably until the bud or whatever comes away clean.
You should be able to see the individual head elements. I do remember that my TSR-8 had the heads caked completely black and solid, and I was thinking "The 32 didn't look like that... that can't be right, surely?" It wasn't.