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:
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.