You also went into the Google Settings app, selected Android Device Manager and made sure both options were enabled?

The app seems somewhat squirrelly to me: my phone reports that a Nexus 7 is a device on the account but it's always 'Unavailable', even though when I run the app on the Nexus 7 it has no trouble finding itself; neither the Nexus 7 or the phone report that the phone is a device on the account - go figure.
Sent from my rooted, debloated, deodexed Sinclair ZX-80 running CM -0.001 using Tapatalk Pro