I have a Nokia Lumia 1020, and my friend has a Lumia 520. We both have the same issue.
We can only stream music via WiFi. 3G doesn't work. Offline playlists are great and all, but only go so far. I'd really like to not pay for Xbox Music because it takes forever to start streaming anything.
I've tried rebooting and reinstalling several times. I even tried the Shrink Storage app, which actually did the trick...for like an hour or less.