I experienced the very same problem just recently (while the feature had worked well for me before).
Interestingly it happened with a very similar prefix (7e59).
It failed at some point during the name change process AFTER renaming all tables and AFTER setting the new prefix in wp-config.php.
My guess is that the chosen prefix is problematic because it is interpreted by mysql as a hex number.
So while I describe the steps that might make the rename process complete below, it might very well turn out to not fix the problem. You would then have to change to a different prefix altogether (maybe one that does not contain any numbers at all)
You can try to fix it following these steps
Make sure that all your table names have been changed to the new prefix.
Make also sure that the prefix setting in wp-config.php has been updated to the new prefix value.
In my case these steps actually completed successfully.
(2) Fix PREFIX_options table
option_name = REPLACE(option_name, 'wp_','XXXX_') WHERE
option_name LIKE '%user_roles%';
(3) Fix XXX_usermeta table
XXXX_usermeta SET meta_key = REPLACE(meta_key, 'wp_','XXXX_') WHERE meta_key LIKE 'wp_%';
Note: change XXX to your prefix
credits to http://tdot-blog.com/wordpress/6-simple-steps-to-change-your-table-prefix-in-wordpress
I guess you have solved the problem by now anyway since 2 weeks have gone by, but maybe this can help others.