This happened in a flat world with the desert preset. I was looking for one of the new villages, and the command returned "Could not find the structure nearby". I checked the command with the desert pyramid, and it returned nothing even though I was standing on top of one, although the mine shafts are located just fine.