I'm experiencing the same problem here. I'm using WordPress 3.5.2 with the version 0.9.4 of the plugin.
At first, it says my tables need to be optimized. When i check the optimization checkbox and the process, it seems to do something. After a moment, it says my database has been optimized, every table have the notice that says they were optimized too.
But when i load the page again, by going in the WP Optimize tab, a notice by each tables says it still need to be optimized. The database is also the same size, nothing has changed.
So basically, it says it works, but it does not seem like it does anything at all for me. I get no error or anything.