Xiangbuilder is leading you in the right direction. If what he's doing doesn't work, make sure that both curves are exactly the same. ALso, you might want to make sure your settings in "loft" are set to default. You may have been fiddling around in there and done something to make this happen. If I remember correctly, you can either make the loft a polygon or nurbs. You can additionally try either one and see if the result is any better.