Hi Kevin,

Re-check that test user really have role, for which you set “Admin Menu” restrictions. Try to re-assign that role to him (remove role, update profile, assign role back).
Check if you use some plugin with admin menu editing functionality, try to deactivate it, to understand if there is any conflicts between plugins.
Yes, show screenshots with ‘Admin menu’ window and what menu items are not blocked.