made of stone,
Americans use the same expressions, but think about it.
The articles 'a' or 'an' are required before those adjectives, and the combination create the same indefinite noun as before, but the adjective is needed to indicate what type of New Orleans, Bush, or Gore out of their many perceived attributes. That's all they are doing, and that's perfectly acceptable.
However, as we seem to agree, in the example from the OP, this was not the intention, so the article is omitted as unnecessary.