I find Google music to work great on the PB. If you have simple browser, you can toggle the user agent and get the less data intensive version of the google music page.
Also, you only need to use the proxy to accept the user agreement for Google Music. Once you've accepted it, you can access Google Music without the proxy. Unblock-US.com, and similar, will allow you to do this.