I've deleted the prefs file, reinstalled software, and repaired permissions. Still nothing.

I think this may have something to do with my router. I haven't messed with it in 6 months, but it would appear the search isn't hitting the internet.

I also did a search for The Beatles to no avail.