Gauss' law is always true but not always useful; your example falls in the latter category. To infer the value of $\vec E$ from $\oint \vec E\cdot d\vec S$ you need a surface on which $\vert \vec E\vert $ is constant so that
$$
\oint \vec E\cdot d\vec S=
\oint \vert \vec E\vert \, dS = \vert \vec E\vert
\oint dS = \vert \vec E\vert S \, . \tag{1}
$$
$\vec E$ is not constant on your sphere, meaning you cannot use (1) and pull $\vert \vec E\vert$ out of the integral and recover $\vert\vec E\vert$ through
$$
\vert \vec E\vert = \frac{q_{encl}}{4\pi\epsilon_0 S}\, .
$$
In your specific example, this is why $\oint \vec E\cdot d\vec S=0$ even though $\vert \vec E\vert$ is never $0$ at any point on your Gaussian surface. The $0$ results from the geometry of $\vec E\cdot d\vec S$ everywhere on the sphere rather than $\vert \vec E\vert=0$.
To proceed you need to use a Gaussian pillbox with sides perpendicular to your sheet because, by symmetry, the field must also be perpendicular to your sheet. Thus $\vec E\cdot d\vec S$ for all sides of the pillbox is easy to compute. If your pillbox passes through the sheet, it will enclose non-zero charge and, using simple geometry, one easily shows that the flux through the back cap will add to the flux through the front cap and you can recover the usual result.