Ok, So I found the problem - but it's not an Quick Fix..
The VMware image found in this Tutorial:
[moderator edit: link removed due to rules violation]
is actually the image of OSX Lion GM, not Lion Retail.
The xCode downloaded from that same tutorial is titled as GM, but does not work with that specific build of OSX. Maybe it did before it was updated to that build.
So I went ahead and found a retail .vdmk floating around the Internet.
I used that to make my own VMware image, fresh install.
To do so you simply Create a new Virtual Machine, Choose 2GB Ram, XXGB Hard Drive size, etc & Create the VM.
In the main screen, click Edit the configuration and add another hard-drive with the downloaded .vdmk attached.
Follow the on screen instructions to install. Make sure you use the disk utilities to format your virtual hard-drive first!
Installation took around 1 hour to install (it hangs on 5/4 minutes remaining for around 20 minutes), and another 30 mins to configure (make sure you download the VGA/Audio Drivers found here to get better resolution and audio working)
Go into the AppStore and install xCode.
xCode is free for Apple ID's linked to developer accounts, which is free too. Click here and click "Members Center" to register your apple ID as Developer
xCode took around 2 hours to download, and around 30 minutes to install. It's got a nice new installer too which kills the iTunesHelper before starting
(But you should make sure you check that iTunesHelper is killed before starting the installation using Activity monitor)
xCode should launch once finished installing and work flawlessly!
Hope this helps someone!