It was that Helios Service Release 2
wasn't compatible with the latest ADT version.
I first downloaded the old release of ADT using the following URL -
http://dl.google.com/android/ADT-22.3.0.zip
Then choosing "Install New Software", "Add Site", "Archive" that I downloaded above.
Worked perfectly well.