The closest situation I saw was when a graduate student $X$ of a colleague $Y$ of mine started to work on some problem, solved it, but was very slow with writing the solution down. During that long and painstaking process, professor $Z$ sent to $Y$ his preprint with essentially the same result and proof. The situation was somewhat awkward but they finally agreed on $X$ and $Z$ publishing a joint paper.
That all could actually be sort of anticipated because both works were just applications of the methods from a paper that appeared shortly before this story to a slightly different problem.
Morals:
I do not think that this situation (when several people jump on the same recent idea and try to squeeze more from it at the same time) is unusual and it may be one of the main reasons why independent but nearly identical works are produced almost simultaneously. So, if your situation is like that, then it is ordinary rather than exceptional.
The submission dates do not really tell who was there first in any reliable way.
It never hurts to negotiate a bit with "the other guy" directly and see if the infamous "priority problem" can be solved peacefully to everyone's satisfaction.
If you really want to make a priority claim, it is a good idea to write a decent draft and put it in the public domain quickly (arXiv is the most obvious choice though you may also want to send it to a few experts who might be interested in your result in your opinion).
There is no point in having 2 nearly identical publications in (almost) the same journal or anywhere.
At last, I have to say that if you are any good, one unpublished paper won't kill you and if you aren't, one published paper will not save you, so whatever happens with this paper, take it easy and don't start a fight or, worse, a crusade. I doubt you'll be able to publish it anywhere once an almost identical work has appeared in print. The upside of it is that you now know someone else (B) who is interested in the things you are interested in. Try to make the best of it.
As to the open-close tag-of-war over this question, I agree that there is no mathematical content in it but, since it directly relates to the "social side" of our craft and is non-trivial, I'd let it stay.