Submitting a note on the falsehood of a conjecture to the journal the conjecture originally appeared in
Submitting your manuscript to the journal the original conjecture was published in is probably a good idea. After all, if the journal published the original conjecture, then the conjecture is obviously in the journal's scope... and so should be a counterexample.
In addition, your submission may well be handled by the same associate editor, who may be able to call on the same reviewers as for the original conjecture. (Of course, it would be a good idea to get at least some new eyes to look at matters, to avoid academic inbreeding.) This could accelerate the review process somewhat.
Beyond that, you likely won't get any preferential treatment beyond what the shortness of your manuscript and the immediate relevancy of your counterexample warrant.
I think you are correct to consider first the journal in which the paper stating the conjecture was published. You should still make an evaluation of whether that is the best place to submit.
(I am in a similar situation myself -- in a graduate research seminar I am leading with a colleague, a student decided to read a 2012 paper which states a certain conjecture and derives partial results. Within a week my colleague showed how to use the tools developed in the earlier paper to give a complete proof of the conjecture. In the last few weeks, I have worked together with the student and my colleague to prove similar, but stronger results. We are now almost finished with the writeup and thinking about where to submit. So the thought process is fresh.)
The main question to ask is: might there be some reason for which the journal who published the conjecture is not the best home for a paper which resolves the conjecture? Some reasons:
1) The journal is too strong.
Top journals are (and must be) extremely selective about what they publish. Resolving a conjecture that appears in a top journal is a distinctly positive sign as to the value of the conjecture, but it is not conclusive. Maybe the conjecture was not such an important part of the paper. Especially if you have disproven the conjecture, is it possible that the conjecture was just not fully thought through by the authors? I cannot help but think of Grothendieck's notorious "Hodge's general conjecture is false for trivial reasons," which adjusted the statement of one of the most famous problems in mathematics -- this is one of the Millennium Prize Problems -- to its current form. And of course this paper of his is famous and important. It just was not published in the kind of journal it would have been if it had "really resolved the Hodge Conjecture". I hope you see what I mean.
This reminds me of a curious feature of the Millennium Prize Problems: you win the $1 million for proving any of the seven problems. Do you win the money if you disprove one of them? The text of the prize does not guarantee this. I think this is pretty dopey (and I would guess that from public pressure alone they would have to cough up the money), but there is some sentiment that if you disprove a conjecture by a "mere counterexample," that may be less exciting.
2) The journal is too weak.
It could go the other way as well. Perhaps what you had to do to disprove the conjecture was truly heroic, and the construction is interesting and important beyond the scope of the original conjecture. If so, consider aiming higher. (I am mildly kicking around submitting the paper alluded to above to a better journal than the one the paper we are riffing off was published in, because that paper gave partial and conditional results towards a conjecture and we can do significantly more than proving the conjecture. My guess though is that in the end the thought of submitting to the same journal in which the conjecture was made will win out.)
3) A paper resolving the conjecture may be out of scope for the journal.
This sounds unlikely, but it can happen and has happened to me. I read an article published in the College Mathematics Journal which ended by asking three questions. The last, most interesting question was one I had previously asked on math.SE. After putting a bounty on it (who said SE reputation is not worth anything?) I got a wonderful answer by Niels Diepeveen. So I immediately wrote up the answer into a (joint!) paper and submitted it to the CMJ. They were surprisingly unpersuaded by the idea that they would want to publish a paper resolving a question that had just appeared in one of their articles. They found the construction too technical to be suitable for their target audience of undergraduates and college math teachers. After many revisions, the paper was eventually published in The American Mathematical Monthly.
In general though, unless you feel your paper is significantly too strong or obviously inappropriate to be published in the journal in which the conjecture it resolves was published, sending it there seems like a good first choice. They certainly do not have to accept your paper, but if they're not going to then they probably need to explain themselves a bit...in practice, if the paper is a bit borderline, I think many referees and editors would find it easier to accept the paper and not look hypocritical.