In both your situations i would first suspect a bacterial bloom.
[Fishyfarts, just a quick comment on your situation--the sand itself was not likely the cause (depending what type of sand, it could have been) but more probably the new substrate was too "clean" and bacteria can very quickly multiply.]
Zorse, to your issue. I have had much the same, only in two of my 7 tanks. I would suspect bacteria. I frankly do not know all the causes of this, but obviously something occurs that causes bacteria to suddenly multiply. Water changes do not help as this only provides more opportunity for bacteria to feed on the organic substances that are present in so-called "clean" tap water that is dechlorinated. I prefer to wait these blooms out, and sometimes they can be gone in a few days, sometimes in several weeks. As long as you are not seeing any sign of stress with the fish, I wouldn't worry. Have a read of the section on bacterial blooms in my article for more background: http://www.tropicalfishkeeping.com/f...quarium-74891/
Carbon would help, unless you have live plants. Plants will help with this better, and since carbon removes nutrients the plants need, better to stick with the plants. But if there are no live plants, carbon is advisable. It will need to be replaced periodically, probably every 2-3 weeks if it is adsorbing something.
The rock might be related. One would have to know what it is, where it came from, what it may have absorbed over time, etc. You might want to remove the two rocks and see if things change. It is one possibility.