I've been having the same problem. I tried your suggestions and nothing worked.

It seems like whenever I force-quit the application, it doesn't work correctly the next time I start it up. I'll search for something and I'll get zero results. I even tried searching for something mega popular, like Fergie, *gag* but nothing came up.

I'm not sure what else to try. Maybe I should fully uninstall/reinstall? That wouldn't be a big deal since I don't have a ton of downloaded music. Any other suggestions would be appreciated!