Originally Posted by hotbike

It's probably scale, and not rust. Studs are made of carbide steel.

I wouldn't recommend any solvents, because it might melt the rubber.

I take it you have a wet basement?