I've made some custom textured armour for a new enemy set. The model and texture display perfectly in NifSkope, object preview and world model. They also appeared properly when they were sideways on the head before I updated Facegen Availability.
But after I updated, the hats on people's heads appear solid black like so:
http://img97.imageshack.us/img97/9206/cwcombathelmblack.png
(From left to right: Before Facegen, after Facegen, world model)

What do I need to do to fix this? I tried searching but the problem is awfully specific and I didn't find anything.

When it turns black, it usually means you:

1) Do not have a normal map attached to the hat.
2) Have an invalid normal map attached to the hat.

According to the poster and the picture, the helmet did appear properly(not black) before the update facegen feature was used. This might indicate that the normal map was attached/set-up properly. Why would the normal map not function only after using update facegen?

I've had lots of trouble when using the update facegen feature. The last time I used it every single helmet in the game appeared sideways.... and it didn't even fix the rotation of my custom helmet. Update facegen only seems to cause problems in my experience.

This might not be the most elegant solution... but it worked for me. You could try rotating the helmet mesh in Nifskope so that it appears properly in-game, but sideways in Nifskope. This is how I ended up fixing my helmet rotation issues anyway. If you try this, make sure you use the rotated .NIF with a new plugin(.esp) that you never ran the update facegen feature on before. I never came across black textures though...

Oddly I tried rotating 90 degrees on the 'p' axis and it shoved the helmet onto the other shoulder if I did a Facegen update. So I deleted the placement mesh file and it put it back on the head, still black.
Then, curiously, I reset the models to their original orientation and saved them with a slightly different name (That wouldn't match the placement mesh) and all of a sudden they appeared upright AND on top of the head AND with textures.

Now the Greenlip Twins (And all the other chums) can be nasty with nifty helmets to match.

The 'Update Facegen Availablility' associates the hat with an EGM file. If you have a new hat you need to have a correspondong EGM file. If you are using an existing hat and only using a texture set to change the texture, then it will 'find' the EGM file for the vanilla hat. And the sideways problem goes away.