I have used BandNames.com and BandRegistry.com - I don't know whether they are still active or of any real practical use in protecting your name - however they are useful for doing a search to see if the name has already been used.
Officially trademarking a name, whether a band or a company cost in excess of $2000, even though the actual fee for doing it is a fraction of that, since this involves a legal search for the name to see if it has been used or registered before and all the associated lawyers fees. It then costs more money to defend your name if the situation arrises where you have to send cease and desist notices. I also believe that the Trademark has to be regularily renewed (every 10 years in the UK).
Trademarking is not protection for your band name if someone can prove first use - they still have rights to the name regardless of whether you have trademarked it or not. Also a Trademark is limited to trading use - if your band is not trading, anyone can use the name.
Ownership is down to first use - usually signified by having sold CDs, played documented live performances or having achieved some other level of recognition that you can produce documented evidence for. This is complicated by locality - first use in one geographic area does not give automatic rights to the name in all areas - two bands that have been going for several years in issolation from each other have not infringed each other's rights to the name.
The other thing to appreciate is that band names are not unique - we have several bands listed on the PA that share the same name (there are at least three bands called Cathedral for example) - and there is rarely any conflict or confusion between them.
Years ago when I was a band manager I was contacted by an American band who insisted we changed our band name - I sent back a list of evidence of proof of our useage in the UK and mainland Europe going back several years and offered them the option of adding USA to their name when playing the UK & Europe while we would add UK to ours when playing Ohio - and then suggested that if they ever came to the UK I would put on a double headline gig for both bands as it would be a great promotional gimick. I never heard from them again. Several years later another US band contacted me asking permission to release some old material they'd recorded under a former name, which happened to be the same name as our band - seeing no conflict of interest (and because the guy was so polite) I instantly agreed.