I was suprised when common shiners added from the creek with plenty of acclimation time showed classic signs of oxygen deprivation within a day or so, considering I had a whole school of them just a few months earlier. Only the 3 golden shiners I got from a bait shop survived, and now their behavior has changed from a happy roaming of the tank to their noses constantly at the surface day and night as if they can't get enough air. The fact that long-term captives are exhibiting the same behavior as new additions within their first couple of days eliminates a lot of strictly "new fish" or "eventual" culprits. Now the ones with the lowest O2 tolerance are dropping in order from smallest to biggest as they would in a tank with no air at all.
Although I got some good suggestions before (like the electricity in the house might be low), people tend to go off in different directions that aren't necessarily wrong but starts a debate that never returns to the subject of the post. Let me ask a simple question, if you had a large tank with a visibly working aeration system putting out plenty of bubbles, and you had proof (either by autopsy or O2 meter) that a single fish was having oxygen issues, hypothetically how is that possible? And if you didn't know, what else could it be? Here's a pic of my very ordinary setup.