Based on what you just wrote, it sounds like you should stick to your Paladin. They make great tanks, but they're not as one-dimensional as a Warrior (once you get a few levels and get spells ... early on all classes are one-dimensional tanks
[You must be logged in to view images. Log in or Register.]). Also, the hybrid exp penalty will be going away in a few months when a post-Velious patch is released, so that should help too.
But if you want to play a Shaman or Enchanter (
EDIT: or Necromancer), play one! All can solo when you can't find a group, and honestly I think you'll have no problem finding a group with either one. The server might have lots of both, but the bulk of them are off soloing, and groups need slowers (or good Necros). When I'm off soloing my shaman (with LFG off) it's not uncommon for random people to /tell me asking if I want a group, so the need exists.
Just my two cents though ... the most important thing is to find something you enjoy and then play the heck out of it.