Is $ALL\setminus(RE \cup co-RE)$ empty?
I'm posting my comment as an answer, at the request of the OP.

Arithmetic Hierarchy AH is a class of decision problems defined as below:

Let $Δ_0 = \Sigma_0 = \Pi_0 = R$. Then for $i&gt;0$, let


$Δ_i = R^ {\Sigma_{i-1}}$.
$\Sigma_i = RE ^{\Sigma_{i-1}}$.
$\Pi_i = coRE ^{\Sigma_{i-1}}$.


Obviously, AH $\subseteq$ ALL. On the other hand, "each level of AH strictly contains the levels below it." (As pointed by Robin Kothari in a comment above). Therefore, $ALL\setminus(RE \cup coRE)$ is nonempty.