Now, I'm an utter complete noob, so my advice might not be worth much, but I use the enchantment shamen in BGs(trying to gear them up to do arenas next season, and get more practice). I am assuming you're using elemental not enchantment shamen, why not try respec or dual spec to enchantment? As I've noticed what Fat Tire said about spell pvp is about moving a lot and keeping distance.

I've deal with warriors and dks like littleburst suggests. I first drop the stoneclaw totem, then earth shock followed by frost shock. After that I use hex to get a breather to heal if I need it. I'm not saying it works all the time, but it works out ok. Granted if I have to deal with 2 or more melees it's a bit more of a crap shoot. Overall I feel I am getting the hang of it in BGs atleast. This works whether I am single or multiboxing, granted if I am in a 3vs1 I rarely have to heal and I might skip frostnova, as I can burn down one fast enough by popping all cooldowns. Granted against people who know how to play and with full vicious gear I don't do too well. It seems that I'm more able to handle the guys who rolled DKs and Warriors since they were so overpowered, and haven't yet gotten to gear them all that well.