Your Pokemon are compatible; you're simply too impatient. Eggs are not always produced instantly, so just keep walking around and checking if an Egg has appeared. If the Pokemon are compatible, every 256 steps you take, there will be a chance your Pokemon will produce an egg. If you ride back and fourth on your bike for some time, eventually you will get an egg.
If you would like to verify that your two Pokemon are compatible, speak to the day care man outside the actual building. So long as he doesn't say that your Pokemon prefer to play with others rather than each other, the chance per 256 steps is above zero and you will eventually get an egg.
For specific chances and interpretations of the day care man's message, see this article.
