heh, your topic is necro as well, as it concerns the effects of the previous patch, not even the latest one ;p
I haven't played LA R'lyeh, but I understand that they have been considerably snipped due to heavy income loss from popkill (and forced upkeep from freespawns?). I'd guess that they are a fairly marginal power now, but no one has taken up the cause of showing how to make them work.
I was playing Hinnom when the patch hit. It goes a long way to making them reasonable - I'd say Hinnom is certainly weaker than Niefl in the early game. Hinnom's starting army is now reasonable (6 swordsmen and 6 LI), and you need to be careful expanding. Gone are the days of just blindly having your initial army conquer indies for 10 turns straight ;p
Some of their units were upped in price, as well.
also, Hinnom bloodhunting now causes something like double unrest. It is pretty irritating
They're still strong, but in no way would I consider banning them from a game for being over-powered (unlike Ashdod, who should be). They're still an EA powerhouse, but one amongst many.