Is there a tree near the pool? I have a large Maple tree in my back yard that drops some unknown substance (sap?) into the pool periodically. It leaves stains like you describe on the bottom that can't be brushed off.

What I've found to work is letting the water get very still and sprinkling Cal-Hypo directly over the stains. Wait 5 minutes and the stains brush right off. I have a plaster pool so I don't have to worry about bleaching out a liner.

I also have converted to the BBB method this year but still keep some Cal-Hypo around for this reason.