Priority for trademarks is established by the first to use a mark for a particular product or service in a given geographic area. Under the facts that you present, you would have priority, even if you didn't register your trademark anywhere.
I suggest that you consult with a lawyer near you with experience with trademarks and intellectual property law to send a cease-and-desist letter, and to review all of your facts.
This answer does not create an attorney-client relationship. It is not legal advice. Please contact a lawyer qualified in your jurisdiction to discuss your situation in confidence, using your factual details. Avvo answers are only general legal responses. Item 9 of Avvo.com's Terms and Conditions are incorporated in this disclaimer as though it were printed here.
First consult and clear, then confirm, and only then confront.
You need to hire a trademark lawyer to help you get a service Mark registration for the consulting services you provide. Getting a fictitious name registration is not enough to protect you. That fictitious name registration is merely for the purpose of enabling people to identify who is using that business name, primarily so they can sue you if they need to for something you do under that name. Service Mark registration, on the other hand, gives you the exclusive right to use that service Mark. That is what you want. You can work with your intellectual property lawyer to register right away with the state of California and to apply for registration right away with the US Patent and Trademark Office.
I did not see you mention anything about clearing your Mark. It may be that your Mark is so descriptive you cannot get it for that someone else had it before either one of you. Since you did not tell us (and you should not tell us) the specific Mark, we do not know the answer.
If the other party has done what you failed to do and used an intellectual property law attorney from the outset, you could be in serious trouble unless you hire one promptly to defend your position and protect your rights. From what you say, it is pretty clear you are not up to the job yourself and need a lawyer's help. From what I can tell, the sooner the better for you.
I am not your lawyer and you are not my client. Free advice here is without recourse and any reliance thereupon is at your sole risk. This is done without compensation as a free public service. I am licensed in IL, MO, TX and I am a Reg. Pat. Atty. so advice in any other jurisdiction is strictly general advice and should be confirmed with an attorney licensed in that jurisdiction.
There are unknown variables that bear on what you can do next.
Many times a fictitious business name is NOT protectable, at all, absent a properly filed fictitious business name statement. For example, if you provide advice on search engine optimization and do business as "San Carlos SEO Consultants" you would have very little, if any, ability to stop someone else from using that same or a confusingly similar name. Same result if you provide advice on environmental issues and do business as "The Stormwater Experts." In those situations, a properly filed fictitious business statement would have provided you with such leverage. But because both simply name the services you provide neither is protectable as a trademark or trade name.
While the California fictitious business name statement does ask for the date when you first began using the name, the date inserted does NOT mean that your exclusive right to use that name began on that date. Those rights, under the fictitious business name statute, begin when all the conditions of the statute are satisfied.
And note: The statute required you to file the fictitious business name statement within 40 days of doing business under that name. You are not in compliance. There is a very good argument, backed by court decisions, that until you do come into compliance you do NOT have any rights in the name you're using because the unlawful use of a trademark or trade name confers no rights or benefits on the one unlawfully using it. In short, you and your own trademark attorney need to consider the possibility that your prior unlawful use of the fictitious business name cannot be the basis for your claim that the new user must stop.
Speak with a California-licensed trademark attorney.
The above response is general information ONLY and is not legal advice, does not form an attorney-client relationship, and should NOT be relied upon to take or refrain from taking any action. I am not your attorney. You should seek the advice of competent counsel before taking any action related to your inquiry.
It is possible that you have superior common law trademark rights under your fictitious business name, but that cannot be determined based on the limited information in your question. Before you can determine whether you have trademark rights, you first need to ascertain whether your use of the name might violate trademark rights that are superior to your own. Indeed, you made a rather fundamental mistake here---you began to use a business name before retaining counsel to conduct a trademark clearance analysis---until that analysis is conducted, I cannot tell you whether you have the right to use this trademark, nor can can I tell you whether you have superior rights over this 2012 competitor.
Further, until the clearance analysis is conducted, we cannot advise as to whether you should register for trademark protection---it is quite possible that you would fail to obtain such registration. While you are the senior user compared to the 2012 business, there may be others out there who are using the name and who have superior rights to both of you.
Further, without knowing the name and how it relates to your business, I cannot tell you whether it qualifies for trademark protection, or whether it is too generic or descriptive to serve as a trademark. In short, it is possible that you can stop this other company from using the name, but you need to do a lot of groundwork before this conclusion can be confirmed. That groundwork includes, most importantly, hiring IP counsel to conduct a trademark clearance analysis and to otherwise advise you. You can't handle this situation properly without retaining trademark counsel.