Trademark rights are not determined by a race to the USPTO (trademark office) but rather the first to use in interstate commerce (or foreign commerce with the US.) If they were in the marketplace before you, find a new name. The tradenames (company names) being in use before is not the prime issue, it is the sale in commerce. They could have opened their company first, but if you were first in the market you should prevail. Finally, if I am not clear enough, the name alone is not trademarked, it is a word or words or logo (or word/words plus logo) attached to the goods indicating their origin.
The above is general legal and business analysis. It is not "legal advise" but analysis, and different lawyers may analyse this matter differently, especially if there are additional facts not reflected in the question. I am not your attorney until retained by a written retainer agreement signed by both of us. I am only licensed in California. See also avvo.com terms and conditions item 9, incorporated as if it was reprinted here.
Trademarks priority is based on being first to either (a) use the mark in commerce, or (b) make application for Federal registration[termed constructive use] and timely prove actual use in commerce to obtain the registration. Trademark rights are based on use in commerce.
Same name used in commerce on similar products as yours! They DO have it trademarked due to use, and you indicate they are first. If they are on the Internet in your state, as is likely, they potentially have you blocked at registration and you are at risk of being found to have infringed. If you apply for registration you might trigger them to oppose you and end up with a USPTO official determination under 2(d) of the Trademark Act that there is likelihood of confusion - in which event registration would be refused and you would be left with a probable losing position on trademark infringement should the other thereafter party sue you. So, you might be forced to change your name for legal reasons by the other company. You likely have a losing legal position if the other party asserts their position aggressively. Whether they will or not is something a good litigator might be able to predict with a fair degree of certainty and depends on how good your representation is and how good their representation is. So, your trademark is at risk. Trademark litigation is very expensive.
If you still want to try to get this name despite the other company's probably prior claim, you need to see the best trademark infringement attorney you can afford and get strategic advice on a battle plan to minimize your risk and maximize your chances. It might be a very expensive uphill battle with less than even chances of success but the more aggressive, better funded, more persistent party frequently wins despite the merits of the respective legal positions.
You may be able to sneak the trademark away from them if you have more money and more determination and a better lawyer. If any one of those is missing you stand to lose.
Bottom Line, you probably need to pick another name and avoid all those risks and expenses and uncertainties.
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.