My sister sent me this on behalf of a friend of hers, and after considerable Googling and mental thrashing around I had to give up - though I'm pretty sure I must have read the story at some point in my extensive horror/SF career. But I haven't landed on a definitive title/author yet, so I thought I'd pass the link along:
Short stories are often tricky to pin down, though, especially if the title doesn't stick in your head (like the Gnoles above). I couldn't remember what it was called, just the bit about everyone breathing together, so it took me years to stumble across Orson Scott Card's "Deep Breathing Exercises" ( http://www.williamflew.com/omni10d.html ) in one of his anthologies after originally reading it in Omni. (Found it again tonight through the scifi.stackexchange site above.)
The other story I can never remember the title/author/source of is about a man who dreams about a mysterious pillar coming out of the sky and causing mass destruction. Eventually he learns that the dream is a message from tiny creatures on the back of his hand - every time he scratches between two of his knuckles he's cutting huge swaths through the landscape. In the end he decides not to scratch/wash his hand for something like a week - the critters are on a different time scale so he figures that will give them a few thousand years to figure out a solution.