Is the set of programs that compute some function other than $h$ recursively enumerable? Let $h$ be a total computable function. Is $S = \{x \mid f_x \neq h\}$
  recursively enumerable?


Originally this was an exercise that restricted $h$ to: $h(x) = x + 1$ . However, it can be formulated as a more general case.

By Rice's Theorem, it is not recursive. Intuitively, 


$S$ is not r.e. as if it was, it would mean that we would know that
$f_x(y)$ halts for some input $y$ in order to check if it has a different image of $h(y)$.
$\overline{S}$ is not r.e. as if it was, we would be able to check if $f_x(y)
   = h(y)$ for every input $y$ (we would check equality for infinite inputs).


How would you solve this problem?

Note: I tried something, but I'll post it as an answer. Some thoughts would be great and really helpful. Any approach to this problem using reduction or diagonalization methods would be useful.
The set $S$ is in fact neither c.e. nor co-c.e. You can prove this via an m-reduction to $\overline{TOT} = \{ x | \varphi_x \mbox{ is not total } \}$ (which is also neither c.e. nor co-c.e.).

Define:

$ \varphi_{f(x)}(y)=\begin{cases}
    h(y) &amp; \mbox{if $\forall z\leq y~\varphi_x(y)$ halts}\\
    undefined &amp; \mbox{ow.}
    \end{cases}
    $

Where $f$ is from the s-m-n theorem.

Then you have that $\overline{TOT} \leq_m S$ via $f$ because, for all $x$:

$x \in TOT \iff \forall y~\varphi_x(y) \mbox{ is defined} \iff \forall y~\forall z\leq y~\varphi_x(z) \mbox{ is defined} \iff \forall y~\varphi_{f(x)}(y)=h(y) \iff f(x) \notin S$