If I had to guess: since your taxonomy seems to be using the same name (and maybe even the same slug?) as WordPress’ stock taxonomy Category, things, well, break ??
On versions 3.x the slug “category” is hard-coded into the query, so you never noticed this. With version 4.0 that’s no longer the case, the taxonomy slug is dynamically changed according to user settings so we can filter out posts by any given taxonomy (and not just categories as before.) So, if I’m right, WPP is asking the database to filter out posts related to a taxonomy with slug ‘category’, and in your case I suspect there are two of them which results in what you see now.
Again, this is just a wild guess. I have too little info and it might actually be something entirely different. I need to replicate the issue so I can understand what’s going on.
Let’s try this: could you please share the code you’re using to register your custom post type -including its taxonomies- so I can try it out here? If the code is lengthy, please consider using pastebin.com or some other medium.