CiviCRM menus don't change for users when roles change

When new users are created - with either old users converted or new users created, the top black and white menu items in CiviCRM match the roles as they should. However, when the authorized roles for individual users change, either new permissions added or old permissions taken away, the top CiviCRM menu does not change to reflect the old roles.

If the admin user runs this script, the menu is fixed for the user with the issue:
http://<oursite>/?q=civicrm/menu/rebuild&reset=1

see discussion thread at:
http://forum.civicrm.org/index.php/topic,21424.msg89879.html#msg89879