I think I was 44 the first time I cleared ZF with my pally / 4x shaman team.. something isn't right.

First, fix your paladin's spec. *Get your sword enchanted for a few +dmg, and Get a SHIELD SPIKE!* Get one as good as possible, but at least a Mithril Shield Spike (16-20 dmg per block). Drop a few points from Anticipation & Toughness to get 5/5 Reckoning. Double attacks help hold aggro. Always make sure you've got Righteous Fury up, and let consecrate aggro build for around 5 seconds when starting a pull with the paladin. It also helps to have some +spell damage on the paladin to make consecrate more effective at holding aggro. Cheap jewelcrafting rings will get you +10-15 spell damage.

Next, magma totems are huge for ZF since there are frequently so many mobs. For me, nearly all the work done on the 5+ minute temple fight was done using only magma totems and an occasional consecrate. You should be going full dps on your shaman spec.. drop 3/3 of Elemental Warding and 1 point from Unrelenting Storm to get 3/3 Call of Flame (more magma totem damage) and 2/2 Improved Fire Nova Totem (for the reduced magma totem threat).

My sequence was always.. pally with typical AoE-prot spec runs into mobs with BoS, Seal of Light, Ret aura, Holy Shield, then pull back to shaman group (within magma totem range) and hit Consecrate. Drop 4x Magma Totems & let aggro build on the paladin for around 5 seconds. Holy Shield again and blast away with Chain Lightning / LB / LB / LB sequence. You shouldn't need to even use shocks in most fights.. just an occasional heal or two on the tank.

You're missing two huge parts of holding aggro.. Reckoning and a Shield Spike, and Retribution Aura & Blessing of Sanctuary if you're not using those too. +3 weapon damage enchant is also a big help. Magma totems will seriously thin groups when layed down 4x with +dmg/-threat talents.

The tricky part of ZF is making sure you always eliminate the Shadow Hunters *first*. Their polymorph on the tank can cause aggro problems. I then take out the healers, then the casters, and finally the melee. Once you manage to avoid that, the instance should be cake at level 46. The hardest parts of the instance should be the cobras at the final boss, but not the boss himself, and the Antu'sul fight if you choose to do it. DPS him down quick while letting Magma Totems/Consecrate deal with the basilisks until he's dead - just clear the entire area around his cave before starting that fight.

Edit:
My shammies always had Blessing of Wisdom - never needed Salvation. I believe my totems were usually 4x magma, 3x healing, 1x mana, 1x stoneskin, 1x strength of earth, 1x earthbind, 1x stoneclaw, 1x windfury, 1x grace of air, 2x grounding.