I can't guarantee that nitrates are the problem here but one of my books
suggest that nitrates should be below 10 ppm for cleaner shrimp.

Certainly if you intend to keep a few soft corals, you need to get the
nitrates down below 10 ppm and much lower for more sensitive species. I
don't know what filtration you have other than the live rock but I would
suggest adding another 10 to 20 of lbs of fully cured (and quarantined) live
rock and when it has settled remove any canister, trickle or wet/dry filters
you may have gradually (if you have one, keep the canister for
carbon/phosphate filters but remove the biological filters and sponges). You
need to make sure that you have enough water flow over the rock (minimum 150
gallons per hour for your size tank and preferably 300 galls per hour).

I hope it helps.

Mark