First, just to be clear, the flux through the base is NOT zero. If it helps to think about it this way, imagine lines of flux escaping uniformly and radially from the point charge and going to infinity. The number of flux lines that will hit the base of the cone depends on the solid angle subtended by the cone - the further away you move the base, the more slanted the sides of the cone get and the fewer lines remain within the cone and hit the base. More precisely, if the solid angle subtended by the cone is $\Omega$, the flux through the base is given by $(\Omega/4\pi)\times(q/\epsilon_0)$. As the base gets further, the solid angle $\Omega \to 0$ and hence the flux $\to 0$. You could check this by starting with the Coulomb formula for the electric field due to a point charge and computing the surface integral of the flux of the through the base (let me know if you aren't sure how one would go about doing this; I will edit to show how). However, the computation is not very illuminating; while I usually don't like thinking in terms of flux lines, for the very simple charge distribution of a single point charge that we have, it makes the physics very clear. Also, I would be careful with making statements like "As the charge moves far away, its "influence" on the fixed base almost vanishes; how can the flux remain constant?". The decrease in the flux doesn't come just from the weakening of the field; the important thing is the fraction of the the flux.
Now, how do we reconcile this with Gauss' law? Well, the answer is that it is generally not a good idea to take surface integrals with discontinuous charge distributions (e.g. point or surface charge distributions) lying on the surface of integration. One way to resolve the issue is similar to what Cicero suggests in his answer - think of the point charge as a small sphere; the fraction of charge lying in the cone is exactly the solid angle subtended by the sides of the cone, i.e., $\Omega/4\pi$, and hence Gauss' law is gives you the same result, even as you take the limit where the radius of the small sphere $\to 0$. The other way to resolve this is to deform the tip of the cone slightly from a point so that the charge is unambiguously inside or outside. If you "flatten" the tip, then the charge contained in the deformed "cone" is 0, but the total flux through its surface is also 0 - the newly introduced top surface contributes $-(\Omega/4\pi)\times(q/\epsilon_0)$, the sides contribute nothing and the base contributes $(\Omega/4\pi)\times(q/\epsilon_0)$. If instead you "stretch" the tip so it contains the point charge, then the charge contained in the deformed "cone" is $q$, but the total flux through its surface is $q/\epsilon_0$ in accordance with Gauss' law - however you end up deforming the tip, the newly introduced top surface contributes $(1-\Omega/4\pi)\times(q/\epsilon_0)$, the sides contribute nothing and the base contributes $(\Omega/4\pi)\times(q/\epsilon_0)$. So, your P.S. is semi-true - Gauss' law, in its differential form is not the problem, but one must be careful when taking surface integrals near discontinuities in a charge distribution.
The problem here is that you've failed to specify a boundary condition.
In an electrostatics problem where you're given a charge distribution $\rho(\mathbf{r})$ and asked to find the electric field $\mathbf{E}(\mathbf{r})$, the answer is the solution to the set of differential equations
$$\nabla \times \mathbf{E} = 0, \quad \nabla \cdot \mathbf{E} = \rho/\epsilon_0.$$
To get a unique solution to a differential equation, you have to specify a boundary condition. Usually, that condition is "the field is zero at infinity".
In this situation, the usual boundary condition doesn't work because the charge distribution is also infinite. To find the electric field, you must specify a boundary condition. Otherwise, the solution is just as ambiguous as trying to solve $F = ma$ without an initial position or velocity.
Once you do that, the symmetry will be broken, making your "$\mathbf{E}$ is symmetric so must be zero" argument fail. For example, one solution is $\mathbf{E}(\mathbf{r}) = kx \hat{i}$ for some value of $k$. You can check it satisfies Gauss's law. The boundary condition is "the field looks like $kx\hat{i}$ at infinity", which is not symmetric.
This issue is subtle: it also comes up when considering gravitational fields in an infinite uniform universe. Newton made the same mistake, thinking that $\mathbf{g}$ had to vanish everywhere by symmetry.
Best Answer
You can use $q/\epsilon_0$ to calculate flux for both cases because that's what Gauss' law says: Just look at the enclosed charge. It's amazing.
Flux for any closed surface is $\Phi = \oint \vec{E} \cdot d\vec{A}$. There are two ways to calculate this quantity:
There are proofs of Gauss' law floating around, but I don't think you are asking for that.
As a side note, one often uses Gauss' law to figure out what the electric field is. Case 1 is very useful for figuring out the electric field at some distance away from your charge. Case 2 is not useful since you can't factor out $\vec{E}$ from the integral. Nonetheless, both cases yield the same value for flux.