woah how did I never see this thread?!
Nicky -- kudos for putting videos of yourself singing relatively difficult music on the internet -- I always think its a positive thing when people are moved so much by music that they learn the parts, sing along, etc., even when they may not be that good at it.
What's funny is that everyone is talking about vocal training --- that can only go so far (but it is important). What you really need is some serious EAR training. Your voice will do its own work if your ears are strong. Try this exercise. You say you've started playing some guitar -- that will help.
I've taught seemingly tone-deaf people to sing pretty damn well in tune with this exercise, over a period of time, with all different tonalities (not just major).
Step one: tune your guitar perfectly. Judging by your range, G major will be a good key to start in here.
Sing the notes G and A. The lyrics are "Do - re - major - second", playing a G major chord while singing "Do", a D major chord at "Re", Gmaj at "major" and Dmaj at "second" (so the notes you are singing: Do = G, Re = A, major = G, second = A ---- clear?)
We're going to do this for all diatonic intervals.
Next is G and B (major third), so you sing "Do - mi - major - third", but this time holding a Gmaj chord the whole time.
G and C is a perfect fourth, so you sing "Do - fa - perfect - fourth", with Gmaj and Cmaj chords alternating.
Next, G - D: "Do - sol - perfect - fifth" with Gmaj the whole time.
G - E "Do - la - major - sixth", again with Gmaj and Cmaj alternating.
G - F# "Do - ti - major - seventh", with Gmaj and Dmaj alternating.
Lastly, G - G: "Do - do - perfect - octave" with Gmaj the whole time.
then go backwards.
this will hammer basic tonality, diatonic intervals, and a simple I-IV-V progression into your head. You need this kind of concrete groundwork to build up from, so that you can sing things in tune, not just from memory of how it sounded in a song, but "ear-logically", relating things to a tonality. Everything you are singing is tonal music, and its not like you're singing every note out of tune, but its definitely not consistent. I think this exercise will help you immensely if you do it slowly. Later on you do it with natural minor and all the other modes of the major scale, and then with all the modes of harmonic minor and melodic minor.
Start doing the exercise with the guitar - the chords will help give you a "safety net" and a very clear progression to relate what you're doing to. Then try it with just a "Do" drone, in all different keys.
Then without any reference. This is the important part. RECORD THIS and listen back to how close you can stay to the original key. This is a very telling exercise, and I think you'll be able to do it.
Make a video of yourself doing the exercise with the guitar and without.