The unexpected stability and anomalous contact angle of gaseous nanobubbles at the hydrophobic solid-liquid interface has been an issue of debate for almost two decades. In this work silicon-nitride tipped AFM cantilevers are used to probe the highly ordered pyrolytic graphite (HOPG)-water interface with and without solvent-exchange (a common nanobubble production method). Without solvent-exchange the force obtained by the single force and force mapping techniques is consistent over the HOPG atomic layers and described by DLVO theory (strong EDL repulsion). With solvent-exchange the force is non-DLVO (no EDL repulsion) and the range of the attractive jump-in (>10 nm) over the surface is grouped into circular areas of longer range, consistent with nanobubbles, and the area of shorter range. The non-DLVO nature of the area between nanobubbles suggests that the interaction is no longer between a silicon-nitride tip and HOPG. Interfacial gas enrichment (IGE) covering the entire area between nanobubbles is suggested to be responsible for the non-DLVO forces. The absence of EDL repulsion suggests that both IGE and nanobubbles are not charged. The coexistence of nanobubbles and IGE provides further evidence of nanobubble stability by dynamic equilibrium. The IGE cannot be removed by contact mode scanning of a cantilever tip in pure water, but in a surfactant (SDS) solution the mechanical action of the tip and the chemical action of the surfactant molecules can successfully remove the enrichment. Strong EDL repulsion between the tip and nanobubbles/IGE in surfactant solutions is due to the polar heads of the adsorbed surfactant molecules.