The nonlinear interaction between two mechanical resonances of the same freely suspended carbon nanotube resonator is studied. We find that, in the Coulomb-blockade regime, the nonlinear modal interaction is dominated by single-electron-tunneling processes and that the mode-coupling parameter can be tuned with the gate voltage, allowing both mode-softening and mode-stiffening behaviors. This is in striking contrast to tension-induced mode coupling in strings where the coupling parameter is positive and gives rise to a stiffening of the mode. The strength of the mode coupling in carbon nanotubes in the Coulomb-blockade regime is observed to be 6 orders of magnitude larger than the mechanical-mode coupling in micromechanical resonators.