After I had updated Google Music on my Nexus S and had uploaded music to my Music Beta by Google account I noticed that my Andorid phone failed to “see” the uploaded music.
If you use Google 2 step verification you may have the same problem, this is how I got around the issue.
1. Go to your google accounts settings page and revoke the authority for you Android device, wait for your device to error out saying it can’t access your google account.
2. Go to Applications manager on your device and clear the cache then reboot your device.
3. Back on your computer create a new password for your device again.
4. Input the new password created by Google into your device for the account that your music is on.
5. Wait for device to access your google account again, give it a minute to sync.
6. Fire up Google Music on your device and wait a couple of minutes.
7. If it all works when you tap the menu button on your device while in Music it will show you the option to link the device to your Music Beta by Google account
8. Enjoy.
Let me know if this helps you.