The thing is our ears our accustomed to what sounds right over something, because of all the listening we have done through our lives. You would be surprised at all the melodies you create, because in reality they are lines that you have forged together from solos that you've heard that are exceptable. Nothing you do is completely original, all licks are spins off others, which are spins on others, etc. Even if you don't know it, somebody before you has done something like it. As for me, I could come up with melodic ideas over riffs for hours. I don't know if it works for every1, but I just do it in my head first (like a mental map) then doing it on guitar, with shred and all that stuff thrown in, so it doesn't sound like a random melody, and more like a solo.
Good luck man!