There is a long discussion of 404 errors when adding a custom post type here. But I was unable to post the painfully simple solution because the topic is closed. Here it is:
Go to General-->Permalinks. Change your permalink structure to something else and then change it back.
This is why flushing the rewrite cache worked. You just need to do it once, however, rather than adding it to your function.