Starting last Tuesday, searching for anything at all in the Nokia Store has resulted in 'spinning circles' (a Qt 'busy' indicator) and no way to tap through to the results of the search.
It's common across all devices and countries, so is definitely a server-side issue.
There's no obvious workaround (though see the user comments below), other than to either stick to browsing apps and games by category (note that you can also re-download applications that you've had previously by signing in, going to 'My stuff' and tapping on 'All downloads'), or foregoing the Store altogether and using a curated app directory or a third party alternative store application (I'm sworn to secrecy on the latter!)
Hopefully the fix is a quick one (e.g. rebooting something) - watch this space.
29 Jan 2014, we have a statement from Nokia: "Our team has been able to identify the issue that has caused the search feature to fail. We expect to be able to deliver a fix for this within the next couple of weeks. Thanks for being patient and sorry for any inconvenience."
This sounds like a platform upgrade on the servers has had an unintended impact on the Symbian Nokia Store and programmers have got to dive in to alter the Store code to work again. Watch this space!
6 Feb 2014, the Nokia Store search has started working again. Well done, Store team, though it's a pity that something was allowed to break for so long in the first place.