I just tested it and when the rights get upgraded, the end user’s My site increased in functionality (Doc libraries, my pics, create list, etc became available).
Do you have Shared Services enabled? Is it possible there are rights somewhere still set to disallow “Create personal site” that is stopping the users from being able to create a My Site? Permissions can also be controlled in central SharePoint admin that will override anything you set at the site level. Have you checked those out?