I was stumped also. I finally found that each user needing the Post Thumbnail Editor to appear needs to go to:
Settings > Post Thumbnail Editor
... and, at a minimum, click the "Save Changes" button. Apparently the "thickbox" dimensions, etc. are user-specific and users must save changes on this page for the thumbnail editor to even appear for them.
Like you, I noticed that nobody else with administrator access could see the "post thumbnail editor" link on the media screen. Editors/authors couldn't either. I think on my end I'll write some SQL to automatically make it visible for all users (for each user, I'll insert a copy of the "wp_options" settings for the admin user), so they don't have to visit the settings page.