Do look at the .htaccess file and check the RewriteBase. It should be commented out or read:
RewriteBase /
It sounds like it might be written as:
RewriteBase /xyz
Where xyz is the name of the folder controlling your subdomain.
Also, what happens when you hit save twice on the Permalinks page?