Hey Kat!
The best solos are melodies - not scales. Playing scales just sounds like you're practicing. You can skip notes, skip stings, and even play notes that are not in the scale, IF they sound good to your ear. The best way to create a melodic solo is to practice playing existing melodies. Pick a couple of songs (preferably old standards) that you know really well. Songs you know so well you can hum or sing the whole melody. Something like "Somewhere Over the Rainbow" from the "Wizard of Oz". Try and play that on guitar. You will quickly find that it is not a scale. It's all over the place. It involves note skipping, string skipping, etc. It is a GREAT melody. If you want something more modern - try playing "Seize Thee Day". It has a nice melody that makes you skip around. All the notes in these melodies are from scales - but they are NEVER just the scale.
Melodies are usually much simpler in rock. You're often forced to play over one chord for a long time - which totally sucks. You can still make it interesting by skipping around and trying to create melodies. Also mix up your techniques. Stay on one note a little longer using a lot of vibrato. slide into notes, bend into notes. There are a million possibilities combining note choice and different techniques.
Make it melodic and make it interesting.
Hope that helps!
Cheers!
pg