Andesite doesn't seem to generate (nor do diorite, granite, etc), but is required to make the andesite alloy, which is vital to most of the machines in Create.
I've checked at the theoretical best spawning height and not been able to find any of the old stone variants even after digging thousands of blocks.

I can confirm. Apparently it was spawning in earlier versions of the pack as it can be found in chunks that were generated earlier.

The only place I found it was in "Andesite Caves".

Ive been able to find it in a vein, along with tuff, gravel and diorite, but very rare in the grand scheme of things. Not sure when or where this change was accidentally made.

I actually was able to find a vein as well, same type coming with andesite, diorite, and tuff.

Its really really rare, but you can find Diorite more often than Andesite and just craft Andesite from Diorite. Create got pain cause of this.