Hi,
The plugin does use all the right hooks and is written using WP standards. It works with all of the standard WP themes and should work with all others too. It’s used by tens of thousands of websites with no issue. However I appreciate that none of that helps you fix it right now!
The issue sounds like either the plugin isn’t activated (which you say it is), maybe you are running some caching plugin that is affecting it, or perhaps it is the way your theme works with hooks and admin view. There again, it could be something completely different!
I think in this case it’s going to be very hard for either the theme author or plugin author to help because the issue is hidden from our direct view, only you can see it working in admin view and we cannot. Without looking through the PHP code in your theme (which I don’t support) there’s no way I can think of to diagnose the actual issue.
In all honesty, the simplest solution might be to try another cookie plugin, unless you have a web developer who can take a look. Sorry not to be of more help this time.