QGIS Difference not working?

I'm trying to simply get the Difference between two sets of lines, but the algorithm returns a copy of either one, depending of the combination of INPUT/DIFFERENCE layer I try. Never the difference.

Both of my shapefiles are in the same projection, and have been cleaned (v.clean).

I tried to dissolve them, but no luck.

Any ideas?

(Using QGIS 2.18.1 over Win7)

---

Here is a picture of the situation. I have 2 sets of roads (red and green). The green network overlaps everything from the red one, but has some other roads in it. I'm trying to get a shape of these extra segments (hence, the Difference). But the result gives me either an exact copy of the red or green network.