iPhone 4/4s Spotlight Search Problem
Under Settings -> General -> Spotlight Search

are the areas you want to search selected (tick on the left hand side), if not just tap the group (Contacts, Applications, etc) to add them to Spotlight Search.