With your new promotion comes new challenges and responsibilities.
Or,
With your new promotion come new challenges and responsibilities.
The issue is comes vs. come, and I’m not sure which is correct, nor why. I’m leaning toward the use of “come” because challenges and responsibilities are plural. Which one is correct and why? Thanks!! 
It’s comes because promotion is singular. I can’t explain this in a more technical way, but that’s the answer. “New promotion” is also kind of redundant.
I’m going to say “come”. Think of it this way: New challenges and responsibilities come with your new promotion.
That’s not the sentence though. Marley has it right. Singular subject has a verb with an ‘s’ on the end. I don’t know why, or if ‘comes’ is considered plural, but that’s the way it works.
If you diagram the sentence, then challenges and responsibilities is the subject, and that requires “come” as the verb.
The subject of the sentence is plural, whether you diagram it or not.
Come is correct.
.
Yes, (I’m agreeing with Mornac) “with” is a preposition. No matter what follows in the preposition clause, it is not the subject. Verbs must agree with the subject. The subject is “challenges and responsibilities,” plural, so the verb must be “come.”
If you don’t agree as to the subject, we have a problem.
It looks like we have the makings of a Great Debate a-brewing.
nm, not sure yet.
I took too long to type my overly verbose answer, so upon preview I’m changing it to “I agree with Musicat, Philster, and Mornac.”
You have to reorder the sentence to see it properly:
New challenges and responsibilities come with your new promotion.
I’m not sure if I was wrong initially, but I’ll say this is probably a better way to write the sentence in any event.
I concur that “come” is what would be traditionally identified as the grammatically correct answer. This is an inverted sentence. In an inverted sentence, the verb still is supposed to agree with the subject. “Challenges and responsibilities” is the subject, hence the verb must agree with the plural.
Identifying “comes” as the subject is an example of proximity agreement, where the verb agrees with the closest preceding noun. Some call it an “error of proximity.”
Another vote for come. I can’t see any case for the plural form of the verb.
They’re both correct. Technical grammatical rules made up by some group of people (probably old men, not that it matters at all) are totally meaningless, all that really matters in language is that you can understand the person thats trying to communicate something.
I don’t know the right terminology, but ‘comes’ is referring to the promotion. It’s describing the relationship of the challenges and responsibilities to the promotion, not describing the singular or plural form of what follows. I stick by ‘comes’ unless someone points out a clearer rule to use.
ETA: I agree that re-ordering the sentence makes it clearer. Maybe it’s just ambiguous and either could be correct.
I agree that “come” is correct. The whole thing sounds terrible, though. My advice is to re-phrase.
How about:
Your new promotion comes with new challenges and responsibilities.
You clearly don’t. I do, though. All the stuff about ‘describing the relationship’ or whatever it is you’re saying - it’s completely irrelevant to the question. The terminology you want is ‘subject’, which is the part of the sentence that determines whether the declined verb should be singular or plural. This flower smells nice. These flowers smell nice. There’s no way that ‘with this promotion’, as a phrase, can ever be the subject of the sentence, and that it can control the verb - so it does not matter that promotion is singular. In this sentence, the phrase “new challenges and responsibilities” is the subject, and as it is plural, the verb needs to be plural as well. The resulting sentence may not be pretty, but there’s nothing ambiguous about it, and there’s no way in which using ‘comes’ is correct.
It should be ‘come’ to agree with the plural subjects
Try telling lawyers that! 
There’s probably a better cite than this one out there, but look here on inverted sentences and subject-verb agreement.
Here’s an example sentence with a similar structure to the one in the OP:
With all due respect, bullshit.
This argument is favored by people who use leetspeak, avoid proper punctuation at all costs, and don’t know the difference between there and their. Arguing that anything goes as long as long as you make your point is intellectually lazy, IMO.