Category searches in Local API seem to be inconsistent. I'm trying to search the department store category (96935005) in the Springfield, IL area. If I search using a search string "SEARS", I can see Sears and I can see the department store category.
I have an iPhone app that's been using category search (with query=*) for over a year now and I suddenly have the same problem. My app is useless with this broken so if someone could take a look, that would be great.