Hardcore Bit proof for discrete log
The usual approach is to identify a randomized self-reduction.  In other words, given a problem instance $x$, you generate a randomized version of $x$, say $x'$, and show how the solution to $x'$ gives you the solution to $x$.

How does this help?  Given a problem instance $x$, you can generate many randomized versions, say $x'_1,x'_2,\dots,x'_m$ (each one using independent randomness).  Now, try to solve each of the $x'_1,x'_2,\dots,x'_m$.  By the conditions of your problem, you know that you'll have a way to solve them, so that a $1/2 + \epsilon$ fraction of the answers are correct: i.e., so that $m/2 + \epsilon m$ of the $m$ answers are correct.

Now, you take it from here.  How could you use that to form a reasonable guess at the solution to $x$?