Actually, its normal. Look at this statement:
After every 256 steps, the chance is taken and if the random value is selected to allow for an egg, the egg shall be created for you to pick up at the Day Care centre. If no egg is produced, then you need to go back and partake in another 256 steps. ~Serebii
You took OVER 256 steps and received an egg. By the time you got the egg and took a few steps, you completed another 256 cycle, and the game decided that you would get an egg.
For example: You walk 509 steps and receive an egg. After 3 more steps, another cycle of 256 steps have been completed, so you got another egg by chance.