I did 4 of these guys last week and all my Paladin Undead items worked, Slay Undead (paladin AA), Deny Undead (spell), and my Ward of Nife (proc).
So, this leads me to believe that the Flesheaters are Undead.
I was a little warry about doing these guys because I didn't know if they were undead or not.. but after I found out that these are Undead.. well, hehe I just loved the fight.
I have been seeking out higher level undead to fight and in UP there are many to do with a lot of fun.
Soloed this guy today he does path by the zone in and hang out for a bit. I saw him while pulling a moktor. I killed the moktor then med back my mana went outside and he was just to the right of zone in standing on the little hill. I pulled him into the zone in with slow and was ready for a long hard fight. I was surprised to find that he was easier to kill than the moktor's I was fighting because I finished him and still had 80m left. Not bad loot got the Wretched pauldrons for the effort.
last night hunting with a group of friends, we pulled on of these only because we couldn't avoid him and he dropped Wretched Pauldrons, they are AC 19 +4 Str +4 Int +4 Wis plate classes wearable/all if memory serves
Kill this stupid alien thing once, Ranger did a great job pulling him through everything. He dropped a 4ac 5str 5sta 3wis 3int 3cha 3dex 3agi Ranger slot item all/all (PoS) =P