In case you use product Flat Data, such cases might happen. For successful applying the Product Label Rules, the Product Flat Data should be temporary disabled. This can be done via System -> Configurations -> Catalog heading -> Catalog -> Frontend, "Use Flat Catalog Product" option should be set to No. After this, product label rule can be applied, the above-mentioned option should be set back to Yes. The final step is reindexing, which can be done via System -> Index Management, for being 100% sure everything works fine, select all checkboxes and press Submit button at the top right table corner.
Nevertheless, it happens that Magento Product Labels extension doesn't work properly due to the conflict with the custom theme/third-party module. Please contact us in the Live Chat or by submitting a ticket so we can investigate your issue and get back with the solution.