i was having a similar problem. with 1.2, i had my wordpress files at
but my blog is located at
with 1.2, i forget what i did, but it involved setting index.php at my root level, rather than in the wordpress folder, and that worked fine.
i uploaded to 1.5 today (completely clean, deleted all but my wp-config.php), and found that simply moving index.php to the root of my site wouldn't work.
my solution, after half an hour of tweaking, was to move wp-blog-header.php to the root of my site as well, and then to open up wp-blog-header.php and (i'm sorry i can't be more specific, i was doing this while my landlord kept knocking on my door harassing me) where it pointed to the wp-config.php file, i modified the path link, so that it read "wordpress/wp-config.php". i'm sorry, again, i can't tell you specifically where, but i know it was just 2 instances, and near the top.
so now when i pull up, "www.mydomain.com", my blog is there, and it appears that my category links are working correctly. hope this can help some people, and sorry if this particular solution has been repeated elsewhere.