Knowing a little music theory, better, a lot of music theory will take you farther. Throw some chords in there, change the melody up a little, transpose(basically changing the key signature of the song). In my Goldeneye remix, I made a whole new bassline for the remix, although to be fair, there was never really any bassline to begin with. But that doesn't mean you can't replace basslines or other parts of the song with your own ideas. Add chords or arpeggios. There's a lot you can do. Just gotta fiddle around and play around till you get something that's different from the source, but still recognizable, and you still like it.
Hope that helps, I can add more, or elaborate on certain things if you wish...