It might seem like a stupid question, but have you guys attempted creating absolutely new users and checking this out? Users with only the default privileges?
These are my results in Firefox in OS X, Iceweasal (Firefox) under Debian Wheezy, Safari in OS X, and Firefox in Windows 7 on geeklog.net. I've provided one screenshot of my user settings page to show that CKEditor is indeed checked.