You're right in assuming this is related to iOS 9. It is not a feature of iOS (7,8,9), FaceTime, Handoff, Calls on other devices, etc. My wife and I have shared primary iClouds with distinct iMessage/FaceTime accounts since iOS 7. Shared call history is not a designed feature but we've occasionally seen that or similar problems crop up (usually at OS upgrade time).
We are dealing with the same thing right now, signing in and out of feature A-Z doesn't seem to fix it. AppleCare's guess is that our iCloud backups became conflated. I'm not sure how to fix that, but I think the most drastic fix would be to try a full reset w/out restore from backup. I'm not ready to do that just yet.
Separate primary iClouds would probably fix this, but I much prefer the advantages to a shared primary ID (single photo library, iCloud Drive).