A funny thing happened when my Orc character Yellow found a Orc stronghold. They kept talking to her like she wasn't an Orc, and therefor wasn't welcome. Just to get her accepted as bloodkin, I did the quest the chief asked me to complete, but she should have been bloodkin by default. Weird.
She also happened to be a vampire lord at the time, so could that have had something to do with it? Maybe she's no longer seen as an Orc but a vampire lord? Or was it just a glitch?
(This was the XBOX 360 version, if it matters.)