First feel the need to make sure you understand how it is supposed to work:
 
The "select different theme" is suppose to control who has permissions to have a different theme than a site wide theme, that is a user specific theme.   The themes that they are allowed to pick are controlled by which themes are enabled in admin/build/themes.  If you only have one theme enabled, then the user will not see the choice regardless of permission.
 
The ability to change a site wide theme is in fact controlled by the "admister site configuration" theme.   You may find it strange, but I guess there just haven't been enough use cases where you'd let someone change atheme, but not hte site slogan or title to justify the feature request.
 
 
Well looks like you figured it out while I was writing this.  But hitting send anyway just ofr the record.

Dave

From: support-bounces@drupal.org [mailto:support-bounces@drupal.org] On Behalf Of adept techlists - kazar
Sent: Monday, February 07, 2011 6:28 AM
To: support@drupal.org
Subject: Re: [support] Select different theme

On 2/7/11 9:21 AM, adept techlists - kazar wrote: 
On 2/6/11 10:59 PM, Carl Wiedemann wrote:

I'm not sure if this has changed in Drupal 7, but in Drupal 6, users 
need the permission "administer site configuration" in order to access 
the path admin/build/themes.

just tested. Very strange that one must be allowed to administer all 
sub-items of site configuration in order to change the theme which is 
under site building.

That one checkbox allows the role to do *everything* in site 
configuration, which is not what Leonard is looking for.

And then why is there a separate permission to "select different theme" 
under System Module in permissions? If I check the "administer site 
configuration" permission and /uncheck/ "select different theme" the 
user can still change & configure the site-wide theme.

"huh?@!"

furthermore, it seems the option to allow a user to change the theme on the account level is now missing (i'm still on  6.19). see att'd screenshot of an account page (the theme is Abarre but i tested with other themes applied site-wide and there still is no button or link to change the theme on the user's account page)

kazar