The only prerequisite for current_user_can() is an existing wp_get_current_user(). The latter is defined in pluggable.php, so you can use it after plugins_loaded.
The _doing_it_wrong() call you are citing in your question is wrong for itself. My guess is that you took that from BuddyPress or bbPress. Both are running into a recursion if they don’t wait that long. There are other, better ways to prevent the recursion.
In some cases, like changing the locale, you have to access the current user object earlier, so waiting for after_setup_theme isn’t even an option.