permalinks and 404 errors

Okay, I just migrated 2 sites of mine to a new server.

Both have the permalinks set to be pretty, using the “Date and name based” option.

One works fine, the other throws 404s.

Switching to uglies solves the 404 problem, but isn’t workable since it’s a 7-year old site that has enough incoming links that I don’t want to break.

Also, if set to the pretty permalinks, attempting to access it via the p=xxx URL does rewrite the URL to the 2007/XX/XX version, but it still 404s.

Anybody have an idea?

Thanks.