For those who are still having issues with adding videos, I hope to have a fallback implemented in the next few days, …here’s hoping. The current fallback method I implemented doesn’t quite work due to a mishap on my part. I will also include a fallback for those who are having trouble with the fancy permalinks not working.
For now those who have trouble with permalinks to albums giving a 404 error check the options page in uTubeVideo Gallery and if it does not have a green “Ok” for the permalink status make sure permalinks are turned on for your site, and then de-activate and re-activate the plugin. This should make it change to “Ok”.