My first World of Warcraft character was a Paladin. I quickly grew bored with the lack of ranged ability and moved on to playing as a Hunter. I later rolled a Druid to have a character I could play alongside Elihu (who also rolled a Druid, Ionathan, who is now 11 levels higher than my Druid). I came back to my Hunter, got caught up in the fun of acquiring new pets, and stuck with Ulfbrikt until level 48. Now I'm back to playing my Tauren Shaman on Cenarius after growing frustrated with the long queue times on 40-49 Stonemaul PvP.
I say all that to say: If you're bored with your current character, roll a new one. You'll learn to appreciate what you had with that character and be able to explore new starting areas and character abilities.
How attached are you to ranged abilities? If you want to step up to your opponent, then roll a Warrior or Rogue. If you want the choice between melee and ranged, roll a Hunter.
Do you want to heal but don't like wearing cloth armor? Roll a Druid (with ranged abilities) or Paladin (without ranged abilities).
Do you want to experiment with playing with a pet but don't want to wait until level 10 as a Hunter? Roll a Warlock.
Tired of seeing the world through the eyes of the Alliance? Roll a Horde character on Cenarius.
In short, roll a new character, preferably of a different race (to start in a different starting area), and level that character to 10. By the time those ten levels are over, you'll know whether you want to get back to your Mage, continue your "vacation," or just keep on truckin' with your new character.
