That's quite large! I can only imagine what I'd do with a tank that size!
Unfortunately, a 10% water change doesn't do much for reducing nutrient concentrations. For example, if your nitrates are 50 ppm, a 10% water change would only lower the concentration to 45 ppm. The next one would take it down to 40 - 41 ppm, the one after that down to roughly 37 ppm, and the next one down to roughly 33 ppm -- and that's only if no source of NO3 is added to the tank in between the water changes. Nonetheless, unless your NO3 is much higher than most of us could imagine, the majority of fish can tolerate it. You'd actually see problems with your invertebrates before your fish if NO3 was high enough to be deadly.
When did you first notice the NO3 reading to be that high -- before the fish died, or after? If it was after, it would be a bit more understandable, as the recently departed were probably sizeable and starting to decay a little before being removed (adding NH3 which was broken down to NO3).
I'd seriously consider adding a refugium to your system with some macro algae. With all that space under the tank, I'd hope you still have a little room leftover to install one without much trouble.
