The plugin should work with any theme, unless the theme is doing something with AJAX or JavaScript. Do you know if the Interface theme does? Did you try a very, very simple rule to ensure it wasn’t related to the rule itself nothing matching?
His instructions are good. If you can see the code when you view source, the plugin should be able to find it and replace it with what you’ve specified. My guess is there’s something that is slightly off like a space or extra line break. Try with a search that is really simple like a single word. This’ll let you confirm the plugin is working. Then expand the find to include more and more elements.
