Having the melody sound wrong has little to do with what scale you choose. A scale is nothing more than a tonality, like major is a bright sound, while minor is a sadder sound. You can notice this if you play several different scales over a chord, the texture and over-all effect of the music changes. In music, at least two contrasting but complimenting things have to go on at the same time. Unison of harmony and melody in a composition should go through different phrases as the music progresses. If not, say staying linear or too similar, the music will become boring. Having a good and convincing contrasting melody over a harmony and doing so without making mistakes takes a good ear, and alot of practice, and a good bit of knowledge about theory, particular voicings.
Mistakes are made when your expressing an idea with the wrong tonality. Each scale over a harmony is equal to a different expression, so it is important to choose the right one. Choose the wrong one and the expression is either weak, or like you said 'sounds wrong'. You definitely wouldn't try to write something happy by playing a minor scale over a major harmony. Even though most ideas can be expressed using similar melody and harmony, most can be expressed even better using contrasting. Although it is evenly correct to be contrasting and similar. The factor is interest and expression.
[Edited by noticingthemistake on 02-16-2004 at 12:02 PM]
"My whole life is a dark room...ONE BIG DARK ROOM" - a.f.i.