It may sound stupid, but I think it's possible that the cat is actually a companion with the Polymorph/Shapeshifter skill tree. That would explain why its quest can't be done, since the reward (besides exp) isn't available yet.
The quest could include the fact that the dog find the cat weird, or something leading you to the idea that it isn't an actual cat. Plus, it's also a pretty neat way to make people want to try this skill tree.
