I recall reading a blurb on algae types, and for the black its said that it was tougher since it had roots and a tougher top. It said the key was to bomb it with chlorine, as for any algae, but that a good brushing was important to break it up and let the chlorine get at it since the roots would regrow from the roots even if it seemed to be gone.

Sounds like that is more of a problem for cement pools where roots could dig in vs. vinyl, but the advice on brushing it harder than a regular green algae could be the trick. If it's really tough you may want to try a smaller brush and do it by hand to break it up.

Good luck with it!