You were LFG for a whole 15 minutes? What we have here is a frame of reference problem... Start a wizard and be LFG for hours or an evening. 8) To answer your question, though, clerics are wanted even at level 1.

/who all (your level range)

See someone in an xp zone you are close to/want to visit

/tell thatguy "Hiya, lvl x cleric LFG, was hoping you need a healer or have a spare spot in case current one wants to bail soon"

Most classes can find a group really quick this way.

If groups seem really thin, do the same /who all, but instead tell them you are considering to start a group and ask them if they'd like to join. Make sure you go to a spot that can support you (I.e don't head to mistmoore if there are 18 lvl 18s in zone already)!

I've never seen a group who didn't want a cleric. Sometimes people will have a sham or druid heal until they find one... sometimes they give up waiting and fill the last spot with a dps, then when you are LFG they are full. Sometimes all the groups have clerics.

Your class is always wanted, you individually just aren't always needed when and where you are LFG.

Red is the right choice. There's a fair amount of misinformation in this thread.
Every single day I have played on Red from level 1 to my current 48 has been played with full groups.

I do not have a static. What's more probable is that I put in more effort than anyone that's ragging on the Red server in this thread. You shout in /ooc, you get one person then say Group is LFM and they start flocking. Idk why this idea escapes people.

I will say I initiated 90% of all these groups which indicates a heck of alot of people really just aren't trying to initiate the group themselves. Red will not disappoint you if you give it a fair shot.

Disclaimer: I rolled Iksar Shaman meaning everyone had to travel to Kunark to play with me. Kurns > Giant Forts> Yeti Caves> CoM and eventually KC and Seb. Safer continent anyway. Seriously try Red.

Level 39 really with complete heal.

Doubly so post level 45.

Also, roll red makes blue itemization that much more meaningful.

If you really want to make friends as a Cleric learn how to root CC and don't be afraid to stick mobs if you have to. Very few Clerics step up to the plate when they are needed for CC and in small duos and trios you'll have to do it all the time.

CH isnt entirely necessary for groups but people always want it especially people in pickup groups. Cleric is one of the easiest classes to get a group on and one of the easiest to get to 60 as well. Its tough for you to get a group sometimes cause there's lots of Clerics out there =P

Root + atone can be pretty good, or even fear and atone.

Root CC is a must for clerics and shaman. If you can do that, you're more valuable than the cleric that only heals in lower level groups :)

Root is a beautiful thing. It will always save you a lot of trouble with healing if there are adds. Root one and have tank move away.
Warriors also appreciate it if you let them just root tank. You'll be glad to do it once you start grouping with epic rogues :)

Sometimes you will get a bunch of tells within ten minutes, sometimes none for hours. It depends on who is online. You can also start your own group, just find a LFG tank or monk or enchanter.

Also keep in mind soloing to 50 is much faster than all but maybe very exceptional duos/trios. Most pickup groups will be very slow exp pretty much anywhere. If worried you can group in CoM during low-mid 40's and hone your grouping skills.