i've always kept algae blennies and have never lost one. all the ones i have kept learned to eat whatever i fed the other fish and nori sheets.
this is actually the first time i've heard of someone losing one. i'm thinking it could be something besides starvation.
btw, they are omnivores.