Check the NEWS Forum, there is a workaround and it works for me on 4s.
JAKE: thanks for this key feature! In fact, I had stopped using the searches, since these were not available on IOS, I am very, very happy to see this functionality, which really is a huge step for the scalability of the app to handle hundreds/ thousands of tasks... which is essential for task management is small projects.
I am sorry that the app is not behaving properly for some people. We have not yet been able to reproduce the problem, but we know how to fix it.
1) Sync the app with Toodledo.com and confirm that all of your data is on our website. If you don't yet have a Toodledo.com account, you can get one for free on our website.
2) Delete the app from your iOS device.
3) Re-download Toodledo from the App Store (Apple will not charge you again).
4) Enter your Toodledo.com account info to sync your data back into the app.
I am sorry for the inconvenience. We are working very hard to figure out what is going wrong here. If you need further assistance, please create a support ticket.