First, you should remove the identifying information from your post, since they can easily find this discussion by doing a web search. Google hasn't indexed this thread yet, but it probably will within a few hours at most.
You mention that you registered your trademark with your state, rather than federally. They may have registered with their state, or may have simply used the mark in commerce without formally registering it with anyone (in the U.S., "trademark rights flow from use."). It appears that they have been in business for well over ten years, according to their website, so they don't appear to be a just-created company. Going by what their website claims, they have senior rights to yours.
You're both using your trademarks under your respective state systems, and both of you seem to be operating locally only. You can both do that, but if they choose to argue about it, you both might be in for some legal expenses. You are in a different line of work, but you're both in personal services type work, and the type of work that you do could conceivably overlap theirs (as you've noted). You are in widely separated geographic areas; it doesn't look like they've tried to expand or franchise in all the time they've had available. If you were to try to go nationwide or to franchise, that might cause some friction.
As to what to do, I'd say it depends on whether they are asking you to cease-and-desist in that letter, or are just mentioning to you that they exist, or what. You don't really make that clear in your comments. There doesn't appear to be a high "likelihood of confusion" given the geographic separation (there are a few dozen "Mike's Auto Repair" shops in the U.S., for example, and their owners don't seem to care).
You might be able to coexist. If you registered federally and then attempted to block their use, you would still have the junior mark, so you wouldn't be able to stop them, and it would likely create significant ill-will. They might or might not be able to block your use; the lack of federal registrations on both sides, different geographic areas, mostly-different businesses, and partly-different names make it hard to tell what a court would decide. It would likely come down to whether the cost of fighting was worth it to either side.