Another thought...
As helpful as scales may seem in constructing solos, I think that they are the sole reason that this 'overplaying' business exists. I think that the main problem is, that people have got hooks and melodies and ideas in their head, but don't know how to play them, so they resort to bumming around in box shapes, not sounding anything like they would want it to.
Try this:
Forget about scales for a minute.
Think about a melodic solo - not one you made up, someone elses' - and try to work it out from your knowledge of intervals.
From learning piano and extensive amounts of theory, I know a little trick that helps you to hear intervals, and, eventually work out complicated melodies by ear:
1st (C-C): The notes sound the same (duh!)
2nd (C-D): Sounds like the start of a major scale
3rd (C-E): Play E then C, sounds like a doorbell (ding dong)
4th (C-F): First 2 notes of the 'Star Wars' theme
5th (C-G): ? It's pretty recognisable anyway
6th (C-A): First 2 notes of 'My Bonnie Lies over the Ocean'
7th (C-B): Sounds like almost an octave. yuk
Octave: (C-next C) Immigrant song (Zep)
After you've practiced recognising these, you'll start to notice the 'in-between' intervals, like minor 3rds and dim 5ths (tritones), and this skill will become automatic, you won't need to think about doorbells or anything, you'll instantly recognise the sound and be able to play it.
To practice, work out little well-known tunes (National anthem, The simpsons, etc.) and sing each interval to your self many times until you can recognise which one it is, then play it.
Good Luck, and have patience :D !
Muz :D