I looked at the FolderPermission table for a couple of my portals where things were working properly and they did indeed have a FolderPermission record for each appropriate folder for "All Users" so, I wrote the following script to update the data on the client site where we were experiencing the problem:

Insert INTO FolderPermission (FolderID, PermissionID, AllowAccess, RoleID, UserID) Select FolderID, 5, 1, -1, null from Folders where FolderID not in (select FolderID from FolderPermission where permissionID = 5 and RoleID = -1) and FolderPath = '' ORDER BY FolderID

This basically inserts a record which grants "All Users" (aka roleID -1) View rights (PermissionID = 5) on all root level folders (FolderPath = '')

Normally, you could just do this through File Manager for each portal but since the site has 342 portals, it was much easier to write the script.

Hope this helps someone else.