Role membership provides security for logged on users. The privacy setting controls visibility to anonymous users. Those are separate systems, so it is entirely possible to have a gallery where anonymous users can see albums that are hidden once logged on.
I can't speak to what might have changed during the upgrade (which shouldn't have), but the fix is exactly what you originally suggested and my answer still applies. You need to assign each user to a role with view permissions to the gallery. There are three ways to do this:
1. Use the Manage Users page to manually assign each user to the role. This would be best for 25 users or less.
2. Open the source code version of GSP in Visual Studio. Configure the gallery data provider, membership, and roles in web.config just like your production system. Then use the ASP.NET Configuration Tool (icon is at the top of the Solution Explorer) to assign each user to the role. This would be best for 25-200 users.
3. Write a bit of code to loop through all the users and assign each one to a role (like I originally suggested). This would be best for 100 or more users.
By the way, I don't really understand your last comment "it's not just existing users, it's all users tied to the db via AD". GSP doesn't store a list of users, so the accounts in AD are "all users" as far as GSP is concerned.
Hope this helps.
Roger Martin
Creator and Lead Developer of Gallery Server Pro