If the tracks are a phasing when combined it means that in spite of using different guitars and / or amps the tracks are still nearly identical. It could be that you playing is very precise or that effects like overdrive or distortion are eliminating the nuances that differentiate the tracks.
1) Try using offsetting one of the tracks
For example you can a free plugin from Voxengo
http://www.voxengo.com/product/sounddelay/You already mentioned you tried nudging one of the tracks so this might not make a difference but it's worth a try and it's easy to undo.
2) If you are using a lot of overdrive/distortion on the guitars try dialing it back a bit.
3) Play the additional track differently - more/less vibrato, just a little bit looser on the timing, different location on the neck, etc.
4) As Kimakze mentioned pan the tracks to opposite sides.
That works great if you limit the number of doubled tracks or if mono compatibility isn't a problem.
5) Re-evaluate why you need the part(s) doubled.
Would that part work just as well or better with different tone or just a bit of delay and verb?