[mindcrime]

Obligatory disclaimer: IANAL. Talk to a real lawyer.

That said, my understanding is that, in the US anyway, you gain a trademark simply by the act of using a "mark" in, well, trade. Even if you don't file for a registered trademark, you still have a trademark if you've been using the mark in trade. What I'm not sure about is exactly what counts as "in trade". If your product isn't launched yet, but you have a website up with a a landing page, does that count? I don't know. That's the part where you need to consult a real lawyer.

I'm also not sure if you have any specific recourse to block your competitor from obtaining a registered trademark which is confusingly similar to your own trademark. This is another place where you need real legal counsel.

At this stage I'm thinking we should just rebrand.

Why should you rebrand? Assuming you really were using the name first, you probably have grounds to stop these guys from using it. Go talk to a lawyer who specializes in "IP stuff". Hey, best case, maybe this will be one of those deals where just having a lawyer send a threatening sounding C&D letter to the other group will result in them backing down.