Do you happen to have a scrap of code I can look at? Cuz I'm doing something similar to that, I think-- I'm getting a left right value, and then modulating it against an up-down value. Like I said, the results are... much worse than I would have expected, so I'm clearly doing something wrong.
Here's some code from my perlin noise code. It uses a cosine interpolation for extra smoothness in ground height, but a straight lerp should work OK too.
// Separate the base and the fraction parts.
int iBaseX = (int)floorf(vInput.GetX());
float fFractionX = vInput.GetX() - (float)iBaseX;
int iBaseY = (int)floorf(vInput.GetY());
float fFractionY = vInput.GetY() - (float)iBaseY;
// Cosine interpolation
float fTL = GetDiscreteNoise2D(iBaseX, iBaseY, pPrimeSet);
float fTR = GetDiscreteNoise2D(iBaseX + 1, iBaseY, pPrimeSet);
float fBL = GetDiscreteNoise2D(iBaseX, iBaseY + 1, pPrimeSet);
float fBR = GetDiscreteNoise2D(iBaseX + 1, iBaseY + 1, pPrimeSet);
float fT = CosInterp(fTL, fTR, fFractionX);
float fB = CosInterp(fBL, fBR, fFractionX);
float fRet = CosInterp(fT, fB, fFractionY);
return fRet;