If the permissions are indeed correct as you say, in both: Usergroup Permissions, and Forum Permissions.
Then it is still possible the permissions-cache is not correct for some reason.
What version of vBulletin are you using, and are you using something like Memcached, Xcache, etc?
IIRC vBulletin < 4.1.6 or something like that was inexplicably erasing some caches sometimes. For me the problem seems to be gone nowadays since upgrading vBulletin.
You can try rebuilding the permissions cache manually:
1. AdminCP > Rebuild > Rebuild Bitfields
2. AdminCP > Update Counters > Rebuild Forum Information
Also, if you edit any permissions manually, this would also update the cache, and might shed light on any problems with permission storage.
Hope this helps.