cannot search messages after upgrading to iOS8!!!

YES, this works! I too have been trying all kinds of methods to solve this issue. This procedure described by joelruby above fixed it. The key is to toggle the spotlight search on and off while still in the foregin language as well as performing a search or two, and give it a little time. After switching back to english again give it a little time but your searches in messages should start working. There may be merit in first trying to search from the home screen rather than the messages app. This solved my issue on an iPhone 6, iPhone 5s, and an iPad mini retina all running iOS 8.0.2.

Settings > General > Accessibility > make sure that Bold Text is OFF, as well as any other text altering Accessibility.

I have tried multiple times the changing language fix. It seems to start working while in Spanish, but then as soon as I change back to English, it stops again and get nothing but blank results. I have a chat with Apple through chat yesterday and they told me to erase my phone as set up as a new one to see if I'm still having troubles with it. Haven't been able to do that yet, because it's requiring a lot more time that I have to do that right now. I really wish a fix would come soon, this is becoming ridiculous that I can't search through my texts. 3 other people in my office with iPhones are having the exact same issue since upgrading to iOS 8.

I posted earlier saying that I thought the update to 8.0.2 had caused the problem to go away (or, more accurately, allowed the language-change fix to work permanently), but of course a couple days after the update it quit working again. I also tried disabling the "Reduce Motion" setting in Accessibility options, and that also seemed to make the language-change fix take hold for a longer period (a couple days), but then it quit working again. And usually, when I do the language switch, it works for only a few minutes up to hours, and then quits. Right now I'm trying a new twist - doing the language switch and getting it working, then doing a reset of the iPhone (by holding the home & sleep/wake buttons for 10 seconds). Several hours after restarting, so far, it's still working. Not holding my breath though.

Slim37, thanks for talking to Apple about this; I really hope they get it. I haven't seen one iPhone user that isn't affected by this problem, so I am amazed they hadn't heard about it earlier. Maybe only very few people use the message search feature, so most iPhone users are unaware or don't care? I can't function well without it, so I hope they fix it soon!

After trying the Language "solution" about 20 times, with every different version of it.....nothing worked. Then I went in to the keyboard, turned of Emoji and Spanish (I never turned Spanish on to my knowledge, so I am guessing that it added to my keyboards when I switched language. Search works like a charm in both the "Messages" search bar and the "Spotlight Search"

Settings> General> Keyboard> Keyboards> English> QWERTY (I already had on QWERTY and never actually went to it, but just letting you know what mine is set on)

It is finally working for me!!!

I have updated my iPhone 5S + IOS 8.1

So far so good.

For those who can't manage to make it working: It might worth reinstalling the IOS from scratch... I know it it hard, but might be the only solution now.

Have you tried resetting your phone (power off/reset) ?

Switching languages worked for me after a few switches back and forth. Fingers crossed.

Gave it more time! Successful

Polish did not work either but Spanish did. This is a wild fix.

Everything works great here after the 8.1 update, over multiple devices. Have you tried restoring an icloud backup to a newly wiped phone?

Switching the language back and forth did not work for me either. I have an iPhone 6. I'll chalk it up to a bug for now and wait for Apple to issue a fix. Supposedly at the end of the month is what is speculated for a fix. Really weird that something like this would be missed at beta. Wasted a lot of time trying to find a fix for this.

Just curious - I was wondering if anyone in this thread doesn't have emoji installed.

I experienced some weirdness today with message search failing a few days after a clean restore from an iCloud backup. Deleted the emoji keyboard, switched to Spanish, and found out that the Spanish and SwiftKey keyboards I installed could search messages, but the english keyboard could not (crazy eh?). I proceeded to delete the Spanish keyboard and switched back to English. Now my search works again, but who knows until when? 😟

Make sure that your Accessibility features for text are all OFF

I am having this same issue. I live in Korea and changing the language to Korean made the messages searchable, but when I changed back to English, the problem returned and I was unable to search all my messages via the search window in the messages app, but then, after about 5 minutes, the messages app crashed, and after that, the problem was resolved. Gotta sat that I'm so far unimpressed with ios 8; seemingly not ready for Primetime.