Pretty permalinks not working

I’m trying to get “pretty permalinks” working on my blog, using the following custom structure:

/%category%/%postname%/

It doesn’t matter what permalink structure I use, anything but the default breaks the site. If I use a custom structure, the following happens to my site:

• The front page is available
• All other pages return a 404, google chrome writes: “Oops! This link appears to be broken.”

When I save the permalink structure in settings, I don’t get any error messages, and it seems like the .htaccess file is generated correctly.

My WordPress installation is on a subdomain: new.mydomain.com — could it have something to do with this?

I’ve run out of ideas, does anyone out there know what could be the problem?

Thanks in advance,

Mads