Yes, $\mathbb{R}^n\setminus E$ has to be path-connected. 

Suppose $x,y\in\mathbb{R}^n\setminus E$ cannot be connected through any path not passing through $\mathbb{R}^n\setminus E$. We can suppose WLOG that $x=(1,0,\dots,0)$ and $y=(-1,0,\dots,0)$.

Now, for each $p$ in $\{0\}\times\mathbb{R}^{n-1}$ you can consider the path $\gamma_p:[0,1]\to\mathbb{R}^n$ going from $x$ to $y$ and passing through $p$ given by $\gamma_p(t)=(\cos(\pi t),0,\dots,0)+p\sin(\pi t)$ (an arc of ellipse). Note that each path $\gamma_p$ contains some point of $E$ by assumption.

Let $\Gamma:=\bigcup_p\gamma_p((0,1))=(-1,1)\times\mathbb{R}^{n-1}$, and define a `projection' $\pi:\Gamma\to\{0\}\times\mathbb{R}^{n-1}$ defined by $\pi(\gamma_p(t))=p$ for all $t\in(0,1)$ and for all $p$ (this is well defined because the paths are disjoint except in the extreme points $x,y$). 

Now, $\pi$ is a locally Lipschitz map, so if $H^{n-1}(E)$ was $0$, then $H^{n-1}(\pi(E))$ would also be $0$, contradicting the fact that $\pi(E)=\{0\}\times\mathbb{R}^{n-1}$.