Hmm, I just tried it too and mine says the same thing. :hmmmm:
I have locations turned on and in "Google Settings" on my phone under "Android Device Manager", both "Remotely locate this device" and "Allow remote lock and erase" boxes are checked.
Do you have those checked also?
Edit: well that's odd...I came here to post this, and when I went back into the Android Device Manager on my computer, it found it.
Perhaps it takes a couple minutes to locate after getting the "unavailable" message??