I have observed this recently..
The Spotlight Search for my iPhone 4S in iOS 5.0.1 is not functioning anymore..
I mainly use this to search for emails, music, contacts, message, etc..
I have already tried restarting the phone and it worked once but after it, it won't search anymore.
Anyone experienced this one? How to resolve?