There is no problem; you are doing it right. Those Pokemon will actually breed together; they will just take a while to do it as their chance of producing an Egg each 255 steps is low.
As long as the Day Care man does not say that your Pokemon prefer to play with other Pokemon rather than each other, the two are compatible and will breed.
Just Game Freak being nonsencical I guess.