Indeed it can. You just have to try longer.
If the NPC say:
>"The two don't really seem to like each other very much."
Man: "But I have to say, those two don’t seem to like each other all that much." / Lad: "But they don’t seem to like each other very much..."
then, there is a 20% chance that an egg will be produced every 256 steps.
This is, assuming that they both belong to you. Here's how Original Trainers and Species of a Pokemon matter in breeding:
![enter image description here](/pokebase/qa-plugin/https-img-proxy/image.php?key=d46b82fc7e0bb777&url=http%3A%2F%2Fs14.postimg.org%2Faf4n0jka9%2Fegg.png)
Credits: Bulbapedia
As long as he doesn't say:
>"The two prefer to play with other Pokémon more than with each other.",
you will definitely get your egg. Just be patient. Some eggs take longer than others.