Abilities:

• Frost Spheres - ~10K HP, killing them drops a Permafrost.
• Permafrost - Freezes the ground in a small area, preventing most creatures from burrowing through it and reducing movement speed over the area by 30%.
  
• Penetrating Cold - Sinks into several enemy targets, inflicting 3500 Frost damage every 3 sec. Lasts 18 sec.
• Freezing Slash - Inflicts 25% Frostrike damage to his target, and stuns them for 3 seconds.
• Nerubian Burrower - Spawns a Nerubian Burrower add.
  
• Spider Frenzy - Increases attack and casting speeds by 50% for each Nerubian Burrower within 12 yds
• Submerge -  Burrow into the ground. Cannot be cast on Permafrost.
• Pursued by Anub'arak -  Anub'arak is pursuing you.
• Pursuing Spikes - Fires a spike through the floor, impaling all targets within 4 yards, dealing 2828 to 3172 damage and knocking them up in the air. This attack ignores armor. Triggers Impale every 1 sec. for 9 sec. Likely targeted at the person pursued by Anub'arak.
• Impale -  Fires spikes up through the floor above Anub'arak, inflicting 14138 to 15862 Physical damage to anyone in their path. This attack ignores armor, but cannot penetrate Permafrost.
  
• Summon Scarab -  Triggers Summon Scarab every 4 sec. for 1 minute.
• Leeching Swarm -  Releases a swarm of insects that attack the caster's enemies, leeching 10% of each target's current health every 1 sec. A minimum of 250 health will be leeched. This damage heals Anub'arak.

The Fight: 

First off, he reportedly hits the tank hard (~20K ish) and a single target Freezing Slash to the tank which stuns them for 3 seconds.    Prepare for some spike damage.

Secondly, we'll see blue floaty orbs moving around above us, Frost Spheres.   They have about 10K hp and ranged should kill them to drop Permafrost on the ground.   The permafrost are big blue patches that slows our movement speed, just movement, not casting, but also prevents Anub'arak from submerging underground.    Only if we tank him completely over the permafrost.   So ranged, with good spatial visualization can try to create big patches of blue frost as much as they can.     Tank Anub over it, and perhaps try to make the patch "grow" by expanding on its edges.   Every part of the giant hit box must be in a blue patch to prevent the burrowing, which is on a timer.    If successful, then it's a tank and spank fight all the way through with max dps time.

We found it difficult to even try to get Anub completely over Permafrost so we didn't bother and just let him burrow to handle that phase.

Thirdly, Anub will cast Penetrating Cold on several players.    It's a DoT, you have to just heal through it (18 sec) I believe every time you see it.   

Anub'arak also summons Nerubian Burrowers occasionally.  These are to be offtanked.   They appear to put a stacking 50% more damage to that tank.   Tank them near the melee for splash damage at least and over Permafrost to prevent them from submerging.    If they submerged, they tend to stay underground and heal and won't appear til the next set of adds.    Which means, they'll just pile up.

Well, should Anub'arak submerge, then we enter another quasi-phase of the fight.   Scarabs will start appearing, they don't much, but can enrage which breaks snares, but can be tranq shotted.   Mostly just aoe them down.

But the major trick is, Anub will persue someone, they'll have a debuff and a big red hunter's arrow over them.    Also, all along the path, Anub will Impale everyone, except on Permafrost.    So the second use for it is to have the one being persued kite Anub all along the permafrost, but mind you, once impaled the permafrost is removed.    So, keep moving to a new one.    Ranged make sure there's plenty around for raid use.    Everyone else, don't be in the way.     Anyways, Anub will switch targets like a few times before he comes up again and you can repeat the fight.    

Which means, you're on a timer again, ranged get that permafrost patch down, tank Burrorwers/Anub over it, and maybe if you're good he won't submerge again.   Repeat above if you do.

Anyways, this all repeats (or doesn't if you're successful) until 30% hp.   This is when Leeching Swarm starts up, no more adds summoned, and I believe no more submerging.    He'll unleash insects that will drain the life of basically everyone.   I believe they are killable, but I also believe Anub will continually summon them now.   What they do is start draining the raid's hp based on their CURRENT health, 10%, and will drain a minimum of 250 hp, and heals Anub with it.

That means, when you're at 30000hp, they'll drain 3000hp from you and heal Anub with it.   When you're at 5000hp, they'll drain 500hp from you and heal Anub with it.    When you reach 2499 hp, draining you for 249 hp, it just won't / can't do it anymore.      Which means, you shouldn't directly die from this, and to mitigate the amount of healing Anub does, you DO NOT TOP EVERYONE OFF.    Keep everyone low, like at 30-40% hp, above I suppose 4000hp at least so you can heal the Penetrating Cold.     Of course, this does not apply to tanks, keep them up.    The raid however, fight off your temptation to blindly heal everything you see.

Anyways, besides that, it's a straight dps burn down.   Kill him before you run out of mana.   So pop CDs, use Divine Sacrifice, all your good shit.    It's probably a good idea to kill all the adds before you push him over 30%, that way you can concentrate on burning him down ASAP.

Hard Mode:

• Penetrating Cold - Sinks into several enemy targets, inflicting 6000 Frost damage every 3 sec. Lasts 18 sec.
• Permafrost - Freezes the ground in a small area, preventing most creatures from burrowing through it and reducing movement speed over the area by 80%.
  
• Impale -  Fires spikes up through the floor above Anub'arak, inflicting 17672 to 19828 Physical damage to anyone in their path. This attack ignores armor, but cannot penetrate Permafrost.
• Leeching Swarm -  Releases a swarm of insects that attack the caster's enemies, leeching 20% (25 Players: 30%) of each target's current health every 1 sec. A minimum of 250 health will be leeched. This damage heals Anub'arak.

For Hard Mode, you only have SIX permafrost to deal with.   The entire fight, it won't respawn.    So you have to use them very carefully, very sparingly.

What we did was knock 1 down in the beginning of the fight.   Tank Anub near it, and get the adds over it.  

There will be more adds, it was 2 in 10 man at least.    They must be tanked over the single Permafrost to prevent Submerges and burned down ASAP.    They also do an 8 second cast called Shadowstrike, basically a shadowstep-backstab on someone which will likely one shot them.    It can be interrupted.   They can be stunned.  So do not let it go off.

In 10 man, we also only went with 2 healers, 2 tanks, so 6 dps and zerg burn Anub down as much as possible during that phase.    Get him to around 65% before the submerge, you have 80 seconds.   That way you can get him to 30% before the next.   If you get a 2nd submerge, you're gonna wipe.

In the submerged phase, ranged shoot down the rest of the permafrost as need be, probably just 4 others and leave the last for later.   DO NOT stand on permafrost.    The goal here is to try to kite Anub a bit, not too long though, no more than maybe 8 seconds, he goes faster and faster and eventually starts randomly (aggro?) targetting other people.     Anyways, kite a bit, then get behind a permafrost, a far one from the raid preferably.   The impale hitting it will reset it's speed and target, and could be any target including you again so keep moving anwyays.

Also, there are scarabs again, but this time they put a very nasty stacking long duration poison DoT on you with every melee attack they do.    So ranged have to burn them ASAP.   Melee might be able to help if they're aggro'd on someone else, try not to get hit too much.   

Anyways, towards the end of this phase, shoot down the last Permafrost and tank Anub/Burrowers over it.    You may need Heroism sometime now to ensure you get the push over to 30% before the next submerge.    For us, as we were learning, we decided to do it after the first set of adds were killed.  If your dps was high enough before, like 50% before first submerge, you prob don't need it, just save it for the Leeching Swarm phase.

At 30%, more of a zerg fest, finish off the set of adds remaining.   The next set, we tanked them off permafrost and let the submerge happen, takes them out of the fight for 30 seconds.  After that, burn burn burn him down before he kills you all.    Remember Penetrating Cold is 6K a tick, keep the raid above that mark.    But not full, except tanks, or else Anub heals a lot more.     DPS race, if Anub doesn't die before those adds return, you'd likely have 4 adds up and wipe.   

And if that's the case, you probably don't have enough dps to do what we did, instead kill the adds some more, when Anub himself is lower, maybe try to let the next set submerge and start the zerg.

Achievements:

The Traitor King - Kill 40 Swarm Scarabs within 30 seconds in 10/25-player mode.

Sounds like just a gather scarabs at the end and aoe them all at once.