No steel wool! It will leave tiny bits of steel embedded in the stainless steel of your pot, and cause more serious rusting.
It's probably just rust stains on the surface, I'd try some Barkeeper's Friend liquid cleanser, with some kind of non-metallic scrubbing pad. Great stuff for stainless steel.
Yeah, I thought the steel wool would be a bad idea. Unfortunately the only beer-specific cleaner I have is BLC and that doesn't seem right. I've been scrubbing the crap out of it and it's mostly gone, but I' afraid that it will spread if I don't get it all off. Hopefully I'll get it all. This is really screwing up my brew day. Thank God I've got a couple batches tapped so I can RDWHAHB