I don't run shamans, but this fight became much easier -- er, I should say, possible -- when I added a macro to my priest to dispel magic off the Memory. I regularly down her on heroic now, though I must admit that I still much prefer drawing Eadric.

I've also got a druid team that just can't cope with Paletress on regular. I try to just burn through the Renew but they're not tough enough. No idea how to do it without something to dispel that awful, awful regen.