First of all, good for you. I don't know if players realize it but on Warmane it is possible to queue for BGs and dungeons simultaneously. When I play on any of my toons I always queue for both.
Oh, really?
So, so wrong.
The 76 - 79 bracket is somewhat inactive for PvP, so that is probably why your Warrior has not hand a chance to whet his sword. When you reach level 80 your luck may be better. Even if battlegrounds do not pop, you can always group with likeminded players to do Arenas and get some much coveted Conquest points. Of course low level PvP is fun, and I suppose the points are of lesser importance.
You can hang out with my level 80 paladin Tzokk if you're going to 80. You may even encounter him randomly as he often invites players to do dungeon runs with him.
You also mentioned that you had multiple toons... At what level? <Ten Twinks> organizes level 10 BGs, <Terrifying Twinks > have been recruiting level 19 players and <Monsters Inc. > now controls the level 70-74 scene on the Alliance. My DK, DBlackknight is a member of that guild.
The guild <We Are Borg> has been attempting to propagate 60-64 and 80-84 PvP as well so you can talk to any of its members with your interests. Of course, you do not have to join a guild to do PvP, only queue, but everything is better with friends. Speaking about f which,
Mijollnir, Valkyree, Lilyandra, DBlackKnight and Tzokk at your service. Let's be friends.