A non-r.e. language whose complement is not r.e. What's an example of a language that is not recursively enumerable and whose complement is also not recursively enumerable?
 A: A language is r.e. if and only if it is $\Sigma^0_1$, which is to say if it can be defined with a formula of the form $(\exists t)P(n,t)$ where $P$ is a computable predicate. 
So languages whose definition requires several nested quantifiers will not be r.e., and their complement will not be r.e.
A few examples include:


*

*The second Turing jump of the empty set, $\emptyset''$. This set is $\Sigma^0_2$. By Post's theorem it is $\Sigma^0_2$ complete, and thus not at any lower level of the arithmetical hierarchy. 

*The set of indices of total Turing machines. This set is $\Pi^0_2$. ("For all $n$ there is a $t$ such that $\phi_e(n)$ halts in $t$ steps".)

*The set of indices of partial computable functions that have a bounded range. This set is $\Sigma^0_2$. ("There is a $k$ such that for all $n$ and $t$, if $\phi_e(n)$ halts in $t$ steps then the result is less than $k$").
The usual way of proving that these cannot be defined with fewer quantifiers is to show that the truth predicate for that level of the arithmetical hierarchy can be many-one reduced to an instance of the problem at hand. 
For example, if $\psi \equiv (\forall n)(\exists m)Q(n,m)$ is an arbitrary $\Pi^0_2$ sentence, where $Q$ is a computable predicate, we can make an index for a partial computable function $g(n) = (\mu m)Q(n,m)$. Then $g$ is total if and only if $\psi$ holds, and an index for $g$ can be computed uniformly from a Godel number for $\psi$. 
