This also happened with me.
The allocation tracker and logcat both had missing columns.
This seems to be happening with IDE with outdated Developer tools.
Make sure you check for updates for the Android Developer tools (https://dl-ssl.google.com/android/eclipse/)
Help > Check for Updates
Current version
21.1.0.v201302060044
After that make sure the tools are updates:
Open Android SDK manager and make sure your SDK tools are up to date.
Window > Android SDK Manager
And make sure the Status columns displays "Installed" and not "Update available" for The Tools.
Current versions are:
- Android SDK Tools rev. 21.1
- Android SDK Platform-tools rev. 16.02
EDIT: I'm terribly sorry. It seems I missed the part where you said you already tried the above. These things worked for me and fixed the problem so I was pretty sure this is the solution.
It seems re-installing Eclipse might be the next step. (Which I never had to do)