This might be idiosyncratic, but I tend to use 'hypothesis' for conjectures whose truth is an empirical question, and 'conjecture' for those where that isn't the case. So I'd 'hypothesize' that rigorous testing would show the FreeBSD kernel to have good SMP scalability properties up to 32 cores but perhaps not above that, while I'd 'conjecture' that a particular problem can't be solved in better than O(n log n) in the general case. The first hypothesis is one you could confirm or refute empirically, while the second conjecture is one you could prove or disprove analytically.
In some parts of science 'conjecture' can also be used to give the connotation of a weaker, less grounded 'hypothesis'. This seems to be particularly used in astrophysics, where 'conjecture' sometimes means 'very speculative hypothesis'.
I don't find the distinction that important, though; it's pretty rare that flipping these two terms causes a real misunderstanding.
Those were my thoughts as well; I normally associate the word 'hypothesis' with the empirical sciences. A hypothesis might be something along the lines of "I believe I shall observe [x] when [y] happens". Justification seems tangential, because it's about corresponding some prediction to some observation.
A conjecture seems more "We observe [x], but there is no way to formally justify why this happens, or if it always happens."
I don't know if there's actually a distinction between these two – it's just my (perhaps naive) perspective.
I'd say using them interchangeably or incorrectly contributes to people's misunderstanding of the word hypothesis, which fuels more than a few baseless arguments against scientific theory in general.
Even correct use of 'hypothesis' doesn't require any particular level of evidence, though. It's somewhat discipline-specific, but a hypothesis could be a complete guess with no real backing. It's just whatever the experiment is setting out to confirm or refute. Especially true in fields where it's cheap to run experiments, in which case the bar for a 'hypothesis' is nearly zero, amounting to just anything testable that you find interesting to design a test for.
Perhaps you're thinking of the debate with creationists and similar people over the term 'theory'?
Marcus du Sautoy has a different approach on the issue, which goes along the lines:
Conjecture: some evidence there
Hypothesis: strong evidence or very strong evidence, such that sciences would have accepted the hypothesis as a theorem. The Riemann Hypothesis mentioned, is the prominent example: Everyone beliefs it's true for more than 100 years, none has provided a full-featured proof BUT even huge clusters failed to find a stretch of evidence that might NOT be correct.
I agree with that distinction. Another notable class of mathematical "hypotheses" are those, like the continuum hypothesis [0], whose truth is formally undecideable but that many mathematicians nevertheless believe to be true in some sense. If this class of statements has any analogue in the empirical sciences, I guess it must be "unscientific" (untestable) hypotheses, about which philosophers (or theoretical physicists) might still find interesting things to say.
Mathematicians also use the word "hypothesis" to refer to a whole implication in the phrase "inductive hypothesis". But it most often simply means the left side of an implication: the phrase "A is true by hypothesis" means that A was assumed to be true—that is, it was the starting point of a proof.
A conjecture has a propositional attitude while a hypothesis does not. A conjecture may depend on a system, but it may be true outside of the scope of that system — think "true but unproved". (Not unprovable like a Gödel sentence!) Once its proof is discovered (made), it becomes a valid hypothesis of the system by its proof which augments that system's domain of truth.
A conjecture is someone's conjecture while a hypothesis is derived from a system itself ("my system has a valid hypothesis"). We don't "derive conjectures" from brains, they're made by persons.
When someone says "my hypothesis is", there is an implicit system they are strictly speaking from (channeling the system? Either way, they're not saying what the believe but rather placing confidence in their understanding of the system strictly spoken from) — they're saying that this is provable within the system we know, but personally they do not have the proof on hand and it may require a little work. ("I don't know all the rules off hand!")
A conjecture has an implicit system, but the speaker has a purpose to say that the system as we know it may have a derived rule we have not discovered. There is "intuition" with conjecture, and "mention" with hypothesis".
In some parts of science 'conjecture' can also be used to give the connotation of a weaker, less grounded 'hypothesis'. This seems to be particularly used in astrophysics, where 'conjecture' sometimes means 'very speculative hypothesis'.
I don't find the distinction that important, though; it's pretty rare that flipping these two terms causes a real misunderstanding.