Here are two things to try:
First, go to music.google.com from a browser, hit the gear at the top right, choose Music Settings, and deauthorize all your devices listed. Now try streaming from the Music app again.
If it still doesn't work, your hosts file might be disallowing the app to stream. This thread describes how to fix it:
http://xdaforums.com/showthread.php?t=1337003, but I found installing ROM Toolbox from the Market and downloading a new hosts file from that app to be the simplest way of fixing it.