I just ran into something similar to this. It had to do with refreshing permalinks. If you go to Settings -> Permalink and just click save see if it fixes your problem. It did for me. In the end I added the following to my functions.php file which updated the permalinks for me. I was using custom post types. Maybe you have a plugin that is doing the same.
add_action('admin_init', 'flush_rewrite_rules');