I viewed the Eclipse ADT documentation and found out the way to get around this issue. I was able to Update My SDK Tool to 22.0.4 (Latest Version).
Solution is: First Update ADT to 22.0.4(Latest version) and then Update SDK Tool to 22.0.4(Latest Version)
The above link says,
ADT 22.0.4 is designed for use with SDK Tools r22.0.4. If you haven't already installed SDK Tools r22.0.4 into your SDK, use the Android SDK Manager to do so
What I had to do was update my ADT to 22.0.4 (Latest Version) and then I was able to update SDK tool to 22.0.4. I thought only SDK Tool has been updated not ADT, so I was updating the SDK Tool with Older ADT Version (22.0.1).
How to Update your ADT to Latest Version
Help
Install New Software
---> Add
Add Repository
write the Name: ADT
(or whatever you want)https://dl-ssl.google.com/android/eclipse/
Developer Tools
and NDK Plugins
Developer Tool
onlyNext
Finish