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 and then Update SDK Tool to 22.0.4
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
In Eclipse go to Help
Install New Software
---> Add
inside Add Repository write the Name: ADT
(or whatever you want)
Location: https://dl-ssl.google.com/android/eclipse/
after loading you should get Developer Tools and NDK Plugins
check both if you want to use the Native Developer Kit (NDK) in the future or check
Developer Tool only
click Next
Finish