Hi everyone, I'm the developer of the premium plugin Olaf was referring to, ThirstyAffiliates.
Just thought I would clear up what is actually the cause here since it looks like no one really knows 100% how to fix it.
The problem is that as plugin developers we normally use init as a point to hook into WP and register our custom post types which is fine. But we also use this point to flush_rewrite_rules(). Which is also fine with one caveat...
You should only flush the rewrite rules once, on plugin activation.
To do so, I recommend checking out this great piece of code contributed by clioweb on github:
https://gist.github.com/871595
Basically, just register a setting on activation, then during your registration of CPT on the first run through you check for the flag, flush the rules, then remove the setting so it doesn't flush again once the plugin is activated.
This is the best method I've found and I'll be rolling it out across all my plugins from now on as should other developers utilizing the custom post type framework.