^^ just to add a bit to clarify - uninstall from admin panel >> left nevigation >> Video Gallery >> Uninstall CVG is a REAL uninstall, which will in turn fix the problem. If you only get to plugin page, unactivate this plugin and delete this plugin, this is not uninstallation. And this won't rebuild the databse, which means this won't fix the problem.
Perhaps @supertnt only did a "delete" plugin, not really uninstall. With the same idea, only deleting/removing the cool-video-gallery folder from "Plugin" folder doesn't uninstall it, hence, won't fix the problem either.