Catacombs is great for leveling. It has Instanced Dungeons that are very easy to level in. Unfortunately, this also means most people now level solo, whereas in the past, people tried to find groups.
I would click your looking for guild box. eventually, someone will try to pickyou up into their guild. Inside a guild, you have a much better chance of leveling yourself. Trying to do it on a cleric is a chore in frustration indeed.
If you were Level 39, I would recommend going into Molvik and finding groups to run with in this bg..you would get RP's and meet people easily and could find a guild this way. 41, you would have to go to Leirvik, and i don't think Leirvik is that active most hours of the day. You could always try that.
you can try Avalon City also, and see if anyone wants a cleric there. The last option might be to spec into smite..Smite clerics can level fairly easy with a few tinderboxes (these are new items that you can buy off of housing that return health/power/fatigue when you are not in combat..last like 30 minutes). Rejuv/Enhance specced clerics can not.