In addition to my previous instructions you have to edit at least the file /wp-content/plugins/nextgen-gallery/products/photocrati_nextgen/modules/lightbox/static/fancybox/jquery.fancybox-1.3.4.pack.js (version may differ), find/replace all rel to data-fancybox-group. There should be 3 of them. This will make the existing galleries to work properly and validate in W3C.
You may need to apply similar find/replace the rel in this file too /wp-content/plugins/nextgen-gallery/products/photocrati_nextgen/modules/nextgen_settings/module.nextgen_settings.php , but as mentioned it isn’t required for existing galleries.
In place of data-fancybox-group you can use something shorter like data-fboxg etc, but as you already guess it must be done everywhere you replaced the rel.