During the configuration of the SharePoint site, per Scot Hillier's book you are instructed to set up the Shared Services Provider creating separate Web Applications for the Shared Services (on port 8080) and Personal sites (on port 8081).
Once I did this I continued on until I got to the Shared Services section of the book (chapter 4) and began playing with the My Site feature. The first thing I noticed (after enabling Self Service Site creation) was that each My Site I tried to create (as various different users) would fail. I began digging through the Central Admin and went to the Shared Services administration. On the 'User Profile and My Sites' section, click the 'My Site Settings' link and ensure that in the 'Personal Site Services' section the 'Personal Site Provider' is your Web Application you indicated as your Personal Sites Application (if you followed the book's instructions in setting up Shared Services it should be the app on port 8081). That got the mysites working for me (from the same domain - read on if you are accessing from outside the domain).
In my test environment, I have the client PC that I access my MOSS installation outside of the domain that the SharePoint Server is in. In order to get the My Site feature fully working in this setup I had to provide alternate access mappings in Central Administration for the Personal Sites Web Application (again if you followed Hillier's setup it should be on port 8081) so that external clients are told to go to a URI that they can access.