Translation:I have already told your parents that I do not like cats.
As a Brit, I put "have" with "already", so the alternatives are "I have already said to your parents" or "I have already told your parents", of which the second is more usual. However, if "my go to phrasing" sounds natural to you, we're clearly not speaking the same language! (There may be a generation gap here too!)
I believe you're right, Aino764046, if I recall the old grade school sequence of tenses lessons correctly, but I don't think that rule is much adhered to these days, and although I am usually an ornery stickler for correct grammar, this example doesn't sound that bad. In addition, the technically incorrect answer serves the additional purpose of letting us know that the speaker still doesn't like cats.
I think the nouns in the dative are because it is "to" them, as in I spoke to them, or I said to them, I believe "I said to them.." would be "Ya skazal im.." or "Ya govoril im.."
As said GeorgeBurns0, it is because of the "to" them implication of the phrase. The same way he would be telling them a story, or explaining them something. There is a "giving" idea very strong. Think it as a "I gave them the explanation that..." ->There is often an idea behind "dative" such as in "dar" in spanish, or "doter" in french.
So I already said to your parents that I don't like cats is not acceptable?
There is only one form of "кошек". Russian language doesn't have articles, so you either conclude from context, or if someone would say "этих кошек" = "those cats", than it would clearly mean "the cats". I am not a native Russian speaker, but I am native Serbian speaker. It is also Slavic language and it also doesn't have articles so there is the same problem with translating :)