I've been pushing for the service providers to offer music downloads on their handsets. In fact, Sprint recently announced such a service. The idea really came to the forefront (for me at least) with the introduction of the Apple/Moto/Cingular ROKR phone. Since that introduction, various similar phones have hit the market.
At first glance, it seems like the perfect combination: I hear a song somewhere, and I instantly download it to my handset (which, theoretically, now doubles as my primary MP3 player). That's the signal Sprint is trying to send, as evidenced by the commercial I saw on TV last night. The guy in the commercial downloaded a song in about three or four seconds. If that's the way it really worked, I'd be a happy camper (assuming the price for the download wasn't prohibitive).
However, knowing the bandwidth of the current 2.5G network, I'm well aware that you can't download a full song in anything approaching that time frame. As backup, how about building a phone-MP3 player combo that can pull songs down from a wireless LAN? That way, I can go into Starbucks and download my music there. This would be a good interim solution, until our 3G networks are up and running in the US.