Tip: Don't use the addon. Have your raid leader watching the debuffs and calling out who to go in based off how many adds are up.
The way we work it. Lust at the start.
One healer and a lock go in for the first totem.
Two DPS and a healer go in for the second.
From here we will simply send one DPS and a healer for the remainder until the ads start to accumulate. Then we will send two DPS and a healer in again to mop up. By this stage Gara'Jal is close to 20% and we simply burn and heal hard. Was never really a struggle on enrage for us... Perhaps you are trying to send too many DPS into the room?
Remember that while the buff in the spirit realm is nice, it will not make up for your loss of DPS on the boss while you are in the realm. As such you should make sure you work quickly in the spirit realm and come out ASAP. As a Disc priest I also spent a large amount of time atonement healing, combined with intelligent use of shields. Atonement if very handy for mopping up in the spirit realm.
You need to post a world of logs link. generically if you can make 1.5% then a kill isnt far off. Logs are kind of mandatory for people to give you meaningful advice.
Also it is possible to two heal the fight, especially if you're overgearing it, but you do need to watch out for the voodoo on healers, since it can screw you out of mana. Obviously disc should be smiting as much as possible. Try to limit amount of melee you send in, but it would be hard in your case, since you're so melee heavy. Obviously make sure you are rolling cooldowns all the time when he gets below 25%, be it raid wide or at least on the tank, loosing someone in the last 10 seconds can mean a wipe. Other than that, the fight is very straight forward on mechanics, so it's a perfect place for your DPS to be forced to improve. There's no clever way to cheese it (well, not any more) and not much leeway, so just good old being forced to become better thing. Make sure everyone prepots and aligns their cooldowns, make sure both of your shammies don't use stormlash at the same time... you know, the simple things.
Ashes to ashes, fade and rust, your mind be broken, your body to dust
We have been doing this fight in hc mode from about the 3rd week it was possible to do hc. (So not world 1st by any means).
For our first kills we found healer dps to be vital.
Until the 1st totem pops and during bloodlust we use one healer to heal and hybrid offhealing (druid NV, HTT from shaman or VE from spriest- they only do this if needed and it rarely is). The other 2 healers dps from start. (3 healing is totally viable). Our resto druid in particular does over 100k dps with prepot and blust (HoTW talent) and even though he doesn't cast another dps spell the whole fight it is a LOT of damage. Disc and mistweaver can obv dps much of the fight. paladins and shaman can also do nice damage over the course of the fight.
People with the link debuff NEED to use damage reduction cd's.
During the final burn phase make sure you use ALL your raid cd's (AMZ, smoke bomb, barrier etc etc)
Make sure your healers inside spirit realm heal themselves enough for mana regen but maximise what they need do on the dps. personally i top myself 1st and then spam the dps refreshing my own buff with a HoT near the end. gives me plenty of mana and plenty of uptime on my personal buff but making sure the dps are well over 20% on theirs.
If you are all over 490 ilvl then you are 15-20 ilvl over what the top 1000 or so guilds needed to kill this boss. This is not to be demeaning but to let you know that all your dps could up their game. are they all using 2 pots/pull on progression? 300 food?, flasks? gemmed and reforged correctly? doing their rotation/priority optimumly? If you think the answer is yes to all of these you are very much mistaken.
Anyway. try and up the dps a bit, use cd's, get the healers to do a few million each ( i think i did about 4-5 million damage on this boss when it still mattered what i did).
It is often useful to make everyone in the raid responsible for suggesting what their class can do for a fight. I do a lot of PUGs of this tier on my alts and am constantly amazed at how little people use their class utility. There is some trash after spirit kings that stacks a move slow debuff that when it hits 10 stuns you. everyone seems to know that mass dispell gets rid of it but i see a lot of shaman that don't know they have totem (talented) that also gets rid of it and a lot of druids that not only don't know that stampeding roar gets rid of it but they can reset it on themselves by shapeshifting. Also mages can blink from the stun and dk's remove stun with IBF.
And don't even get me started on the people that don't utilise symbiosis to it's utmost.
I hope the 1st half of this was helpful and that u forgive the rant in the second half