Have you tried saving any kind of permissions since noticing this issue, even though the permissions look correct and the settings remain unchanged? Saving them should rebuild vBulletin's cache of permissions, which may have gone missing somehow.
Another thing you can try is "Rebuild Forum Information" under vBulletin's Maintenance Tools in the AdminCP.