Ammonia- Zero

PH- fluxuates between 7.8 and 8.0

Nitrite- .25

Nitrate- off the chart

I did a 20% water change and noticed no difference in my nitrate readings. Since then I have added a protein skimmer and have done a 50% water change. I again tested my tank, ammonia and nitrites are both at zero, ph is at 8.0 but my nitrates are still to high, chart reads between 40 to 80 ppm more so towards the later. Should I perform another 50% or greater water change? I am at wits end as I don't know what to do anymore, the algae is still growing but has slowed down greatly but my nitrates are still to high. I see from reading some other posts that crushed coral can be a cause of high nitrates. Should I change out the crushed coral and go with live sand? I also must admit that I was over feeding the fish due to some poor advice from a local fish store employee. I am now only feeding my fish once a day. Should I feed them more or stay with the schedule I have them on right now? I am fearful of losing my fish as I am a new aquarist. I hope I have provided the right information for some one here to help out. If not I will be sure to provide whatever information will help. Thanks in advance for any help you provide.

75 Gal. FOWLR tank. Fluval 405 pump. Aqua-Medic Turboflotor 1000 250g protein skimmer. Maxi-Head 1200 pump. Live aragonite with 45lbs live rock. Stars and Stripes Puffer, Volitan Lion, Blue Koran Angel, Snowflake Eel, Picasso Trigger, Blue Damsel, Bluefin Damel, Domino Damsel. 10 Snails and 4 hermit crabs.