Big Bagel! I have the same problem, and switching to a non-custom permalink structure DID fix it.
So now that I know it’s an issue with the custom structure I’m using, can I fix that?? Surely I can’t be doomed to the default settings?
What I’m using is just a plain old wordpress-suggested structure, the radio button they label as “month and name”. Everything was working fine before I migrated my site from a subfolder to the root folder.
Now the only thing not working is my custom post type. Everything else — the single posts, the taxonomy pages — works fine.