We also have our permissions based on groups. I haven't had the need to give permission individually. We are on ePDM 2013.
I would check to make sure the group has permissions in the folder first, then check the transition they are trying to use, and then the state the transition is going to.
I have found subfolders will inherit the parent folder's permissions, untill you change that subfolders permission specifically. Once you change it, it will not gain the parent's folder permission. ( it has been a while so I'm not 100% sure, but I believe the only way to get the subfolder to inherit again is if you change the permissions back to the parent's folder or delete all permissions for parent and sub and start over.)
We have a pretty rigid folder structure and the only way to add a folder is via a template and can only be done in specific areas.