The sand doesn't need to be changed, unless you were previously using Bacquacil or some other chem system that goops up the sand. But if it's a chlorine pool, and has always been, then no need to change it. One of our mods, Poconos is going on 14 years with his sand, and I think Watermom's at 11 years with hers.

If the pool is blue/cloudy, and you're not losing chlorine when testing at night and again before the sun hits the pool in the morning, then most likely the algae is dead and just needs to be filtered. Assuming your filter is working properly, you can also add a handfull of DE to the filter to help catch finer particles. If you're still losing chlorine overnight, however, then you're still fighting something in the water.