I've read of issues of permalinks and subdomains. I consider my issue a bug as I have resolved it manually (i.e. not via WordPress software or files).
I run WP (single site, not multi) on a subdomain. When I try to customize the permalinks to something like http://mysiste.domain.com/%category%/%postname%.html it saves the permalink as /http:/mysiste.domain.com/%category%/%postname%.html. For some reason it moves around one of the / marks. I've tried disabling the .html for pages plugin, I tried everything I could think of.
Finally I was browsing around the database in phpMyAdmin and was looking at the settings. In the settings it shows the URL just as I had seen it in the WP settings with the / mark not in the right place. So, for the heck of it, I edited that entry to reflect the correct syntax.
Low and behold permalinks now work on my WP blog. No more 404 pages on the blog. Since it is working I am taking it that it's an issue in WP that is moving around the / marks.
For those that want to do this fix or attempt it, under phpMyAdmin go to the options table. Then, about page two of records you will find a record with an option_name of permalink_structure. Edit that to what you want it to be. In my case it was http://mysiste.domain.com/%category%/%postname%.html.