There are a few prerequisites to getting my sites working.
You will need to create an SSP to manage user profiles and my sites. This is done from Central Administration > Application > Manage this Farm's Shared Services. If you do not have an SSP defined, you'll need to create one. In the settings page, you either have to provision either a new web application (preferred) or specify a path to host the my site collections. You will also need to create a web application (preferred) or allow sharepoint to define an SSP host location in an existing web application. After the SSP is defined, you'll need to open it and make sure the My Site location is defined under User Profiles > My Site Settings. Once this is done, you should be able to provision My Sites.
If you have an SSP defined, you may want to check the settings under User Profiles > My Site Settings to insure they are configured properly.
Hope this helps!