The substrate change-over caused an imbalance in the tank's nutrients. Much the same as a "new tank." This is frequently the cause of sudden algae, in this case diatoms (brown algae as it is called). The organics in the substrate are essential in a planted tank, and bacteria (with the help of snails
) break organics down into nutrients, and the plant roots play a big part in this. Having changed the substrate, all the organics disappeared, so the water biological stability was suddenly gone, hence the diatoms.
The type of algae is another issue, in this case it was diatoms which could just be the above, or it might indicate silica sand. When you have checked the composition of the black sand we'll know. I would not suspect black sand of being silica-based, as silica is whitish (like the sand in sand traps on golf courses) made from silica quartz. But let us know.
Another source of silica is tap water; in some areas it may be higher in silicate, and this contributes to diatoms. As does low light. I still suspect it was the imbalance though. That means it will not last. Remove what you can. So-called "algae-eating" fish like Otos, Farlowella, Bristlenose plecs, etc., will eat this readily. I do not recommend buying fish just for this, but if any of these happen to be in the tank, they will handle it. But once the balance is established again, probably end of the diatoms.