I started working on AAs at level 54. Since my Barbarian Warrior is well-tweaked (255 Str since level 18 or so), I worked on other stats first, like Agi, Dex, and Sta (improved the lowest stats first). Then I maxxed out the level 51 hp regen skills. When I hit 55, I had an Axe Of Destruction, so it made sense to max my Weapon Affinity skill to maximize the proc damage (it takes 25 AAs to fill all 5 ranks, but it's definitely worth it). Then I maxxed out the level 55 Combat Fury and Combat Mitigation AAs (another 24 AAs total). Now, at level 61, I'm going back and filling up the level 55 hp boost, Finishing Blow, and Avoidance skills.
My philosophy toward the warrior class is fairly simple. By being able to kill enemies more quickly, you're saving yourself a significant measure of damage over the long run and you're helping the casters in your group conserve mana by not having to use as many nukes during a typical pull. My warrior uses a Runed Green Legion Longsword and frequently hits for over 200 points of damage. With the new Triple Attack skill and 5th rank of Weapon Affinity, I'm wiping out mobs pretty efficiently.
That's not to say that other skills aren't important. They are. But if you're a Warrior, it really is in your best interest to focus on class-related skills first.