What exactly does he say? If he says they "don't like each other", it is actually fine and you don't need to do anything. They will breed eventually -- they will just do it more slowly than other pairs (see the link below for more detail on that). You only have a problem if he says they "prefer to play with other Pokemon", in that case the chance of producing an egg per cycle is 0. Otherwise, it will definitely happen eventually.
http://bulbapedia.bulbagarden.net/wiki/Pok%C3%A9mon_breeding#Breeding_rate
If you want to get eggs the fastest way possible, bike/ride around on the route or areas around the day care. The game randomly decides if you will get an egg with every 256 steps you take (one egg cycle), so the faster you can burn through this, the faster you'll get eggs.