I was tanking in Naxx last night and while I had about 2k more health then the other tank the healers were having to work harder to keep me up. I am wondering if I need to focus more on avoidance stats or keep gemming Stam.
Yes I would suggest losing some block in favor of more avoidance. Block is ok at low level but for raid bosses it is really ineffective. You should notice a lot more survivability with extra avoidance. Also remember there are defense to chest, shield, and cape. As you lose some of those starter high defense pieces you will likely need those enchants, especially to keep stamina gems.
Well, in general your avoidance will go up naturally as you get gear upgrades, that's the short of it. Also, itemization for tanks (especially warriors) favors shield block, which really hurts avoidance.
With the new Diminishing Returns (DR), some people believe that stacking defense beyond 540 is a conservative way to gain avoidance, especially since you are going for upgrades. For you it's something to consider as you drop blues, you will lose def rating and gain avoidance, so keep it up with def enchants (They are options for shield, cloak, and chest).
You are on the right track as far as enchants, although you could use something on your shield (I suggest 20 defense, it's what I have on that shield myself given its low def value). Also, you will naturally enchant your cloak when you get a new shiney, presumably.
Your gems are mostly ok, the only one I object to is the parry/stam. Never gem for parry, even as a DK, and people will be seriously evaluating that statement even when the rebalance it in 3.2, but for now go with 24 stam. If you want avoidance, add a little dodge (Since the slot is prismatic, you can stick a red gem and not worry about bonuses).
Having said that you are really behind on threat stats, you need 17 more expertise SKILL (not rating; 26 skill is soft cap), it is crucial for warriors. I would gem for expertise or expertise/stam until you get enough expertise from your nax gear. After that, work on hit rating to get to 263 (but as a warrior, expertise first).
You can grind out enough badges for T7 chest, although if you run nax enough you should get an upgrade before then. OS10 will also lead to t7 gloves.