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.