Depending on what caused the stains, a good shock probably will get rid of them (meaning attain shock level and hold it there for a few days to see if it makes a difference). Do you have metals in the water? Does the stain end where the waterline is?

It's really hard to answer the question without a good set of water test results...

Janet