That shouldn't really be happening. They are in the same egg group, they only need to share one egg group, so that should be fine.
Unless they are the same gender I wouldn't know what to tell you.
>Different Egg Groups, same genders or Undiscovered group:
The Pokémon are incompatible and therefore will not make an Egg. The Day-Care Man will say: "The two prefer to play with other Pokémon than each other."
This is the only situation in which, according to Bulbapedia, it gives you that "The two prefer to play with other Pokémon than each other." message.
Maybe it's a glitch or something like that.