You should search with product titles, not with category names.
Have you updated the theme to 3.0 version?
Please do this.
Before update delete “woocommerce” folder in the directory wp-content/themes/legenda/ and it’ll be reuploaded from a new theme package.
Also update all required plugins http://www.8theme.com/download-plugins/ .
Don’t forget to create back up of your files and database before starting update process!