I've been playing a lot of warrior in Play lately complete with some expert cards. Having come from other classes before that I'm guessing a problem a lot of you are having is playstyle. Hearthstone (or any good CCG) is not something where you can jump from one class to another and use the same approach with different cards.
Warrior IS rough without expert cards, but it's far from unplayable with the right deck. I threw together the following from my own experience and I'll try it later tonight and report back.
Big point to new Warrior players is that you want to stay on the aggressive end whenever possible. Your goal is NOT to trade for board control, but attack aggressively (using charge.) This does give your opponent the chance to trade, which may seem terrible at first, but it's all about pacing. When you can keep this up, each minion you play eats a removal spell, takes out most or all of an opposing minion's health, AND deals damage to the opposing hero. Why does this work? Warrior cards are very cost efficient on the whole. You kill what remains on the board with your own removal, including weapons, and by turn 8 or so you only have 1-2 cards left to their 4-5, but they're at or hovering near lethal range.
If you try to build or play your deck half way in between this is where you'll encounter problems. Warrior control needs more expert cards to hit its stride, but a lot of the cards needed for aggro are right here. Even my warrior Play deck has uses a very large number of basic cards, and probably a majority are basic + common.
EDIT: Checked, and my current deck has 14 starter cards, and 13 commons.
EDIT2: Record with that deck: 2:2, replaced 2 gurubashi with 2 3/2 raptors and went 4:4 with the 4 losses being against well constructed decks that any other all-basic deck would likely lose to as well. Considering every deck I lost to was running plenty of rares I'm content. I was also playing at like 3am, and I tend to run into a lot less casual decks around this time. I think I've got all but one game up at http://www.twitch.tv/shalune/b/482281631
I noticed while making these decks and playing that a big problem warrior has in Basic cards is a lack of good turn 2-3 minions. Both my Basic, and Expert Warrior decks are stacked with 2-cost cards to fuel the aggression, and it felt weird lacking consistent turn 2-3 board presence. Fortunately, for those looking for more than a novelty deck, a lot of the best 2-3-drop minions for aggressive Warriors are common:
Shattered Sun Cleric (Basic card, but gets so much better when you have more 2-drops to play it on)
Edited by Shalune on 11/23/2013 2:38 AM PST