It's not working on mine as well. Is it like iTunes radio in which it works as long as you're using a US-based iTunes account or do you have to be physically in the US?
I'm in Canada and I got it a few days ago. I also heard that people in France are getting it. It doesn't needs a new beta, it just rolls out over the air and you'll get it soon.
Also, it works hit and miss for me at this time but it will likely improve over the next few weeks.
Is anyone else having an issue checking Spotlight Suggestions and Bing Web Results in Spotlight settings? I am unable to check either. Upgraded OTA. Spotlight will only search locally.