If all those things didn't work, then I would get in touch with the company that put in the pool - maybe something with the plaster - They would probably be able to help you out. There is also a stain kit by Jack's Magic that helps to identify stains. My opinion since your pool is new is to get in touch with the contractor and ask his opinion.