I'm having the same issue. This is a brand new Mac (a week old) that I am building from the ground up - so none of my files should be corrupted or filled with cruft. I am carefully adding one application at a time. I was following along with Don McAllister's screencast and found the Safari bookmarks (stored in iCloud) won't search. They do, however, come up in Spotlight.