We announce the discovery of a low-mass planet orbiting the super metal-rich K0V star HD 77338 as part of our ongoing Calan-Hertfordshire Extrasolar Planet Search. The best-fit planet solution has an orbital period of 5.7361 ± 0.0015 days and with a radial velocity semi-amplitude of only 5.96 ± 1.74 ms–1, we find a minimum mass of 15.9^{+4.7}_{-5.3} M ⊕. The best-fit eccentricity from this solution is 0.09^{+0.25}_{-0.09}, and we find agreement for this data set using a Bayesian analysis and a periodogram analysis. We measure a metallicity for the star of +0.35 ± 0.06 dex, whereas another recent work finds +0.47 ± 0.05 dex. Thus HD 77338b is one of the most metal-rich planet-host stars known and the most metal-rich star hosting a sub-Neptune-mass planet. We searched for a transit signature of HD 77338b but none was detected. We also highlight an emerging trend where metallicity and mass seem to correlate at very low masses, a discovery that would be in agreement with the core accretion model of planet formation. The trend appears to show that for Neptune-mass planets and below, higher masses are preferred when the host star is more metal-rich. Also a lower boundary is apparent in the super metal-rich regime where there are no very low mass planets yet discovered in comparison to the sub-solar metallicity regime. A Monte Carlo analysis shows that this low-mass planet desert is statistically significant with the current sample of 36 planets at the ~4.5σ level. In addition, results from Kepler strengthen the claim for this paucity of the lowest-mass planets in super metal-rich systems. Finally, this discovery adds to the growing population of low-mass planets around low-mass and metal-rich stars and shows that very low mass planets can now be discovered with a relatively small number of data points using stable instrumentation. Based on observations collected at the La Silla Paranal Observatory, ESO (Chile) with the HARPS spectrograph on the ESO 3.6 m telescope, under the program IDs 079.C-0927, 081.C-0148, 087.C-0368, and 088.C-0662.