Lovely plugin, I've tried most on this cookie issue and none are quite right, yours is pretty close. I've made a small hack for a major tweak but really it should be this anyway. :D
These two I did for myself:
When you register your cookie post type you shouldn't be doing a conversion on EVERY pageload of all the old post meta, there is a Action Hook for version upgrades.
Secondly, that conversion shouldn't be using the entirety of a WP_QUERY class instance to load the cookie post types use get_posts() instead, quicker, less memory use and it doesn't mess up the URL query.
What I haven't done is worked out how to stop the cookie jQuery file (not the main one, people might be using that) loading if the "agree" button has been pushed. Why load a file/make a HTTP request for something you don't need anymore?
Other than that I'd say this is the best Plugin out there for cookie notification, it doesn't slow down the site more than it has to, it doesn't add any DB queries (just makes the wp_options load a little bigger), loads JS in the (ideal) footer and is highly configurable in a nice UI (although you could shrink the load a little my not having so much custom UI), and I haven't seen any PHP notices which happens more than it should in WP plugins).
All in all, currently 7/10, with my 2 tweaks and request 9/10, and a point left for improvement. :P
Good Job. Look forward to trying any of you other plugins.