Look at the rock of the bottom of that last image – it’s got sandy-colored lines going through it. Presumably, you are drawing the sand first, then the rock on top.
This tells me it’s not “black lines being drawn” through the textures, but that parts of the textures are not being drawn. Since it happens when you stretch vertically, this almost certainly means you are creating a mapping from old pixels to new pixels, without interpolating values inbetween in the new texture.
For instance, using the mapping (x,y) --> (x, 2y), the points will get mapped like (0,0) --> (0,0), (0,1) --> (0,2), and (0,2) --> (0, 4). Notice that no points in the source texture map to (0,1) or (0,3). This would cause the background to seep through. I bet if you change it to stretch horizonally, you’ll see vertical lines.
What you would need to do is map the other way: given each pixel in the target texture, find its value in the source image using the inverse of the above transformation. You will probably get fractional values pixel-coordinates, so you will want to interpolate values.
I am not familiar at all with XNA, but there is probably a more convenient way to do this than by hand.