You really didn't need to change the sand, unless you've been through a Baq conversion or added something that gunked it up. The other three mods on this site have over 10 years on their sand apiece, and is still working fine. I've got 3 years on mine, but would be approaching 10 years had I not decided to try zeo.

You can use a cup of DE to help the sand filter. First you need to test and make sure the filter's not passing stuff through--take a couple of cupfuls of DE and add it through the skimmer, then watch the returns to make sure it doesn't blow back into the pool. If not, add enough DE to raise your pressure by 1 psi (that pressure change comes slowly, sometimes up to 30 minutes or so), and it will coat the sand, helping to pick up smaller particles.

You want to continue to hold your pool at shock level until you're no longer losing any chlorine overnight, but that's going to be hard to tell when you don't have the appropriate test for it, which is the best feature of the test kit I described above. It's good that there's no green left--make sure you brush the pool really well and don't have ANY green before you start letting the chlorine come down.