Early Bird halves the sleep duration. When the Pokémon is put to sleep, the number of turns it will remain asleep is preset (the range depends on the generation). This number of turns is halved for a Pokémon with Early Bird, rounded down if it is odd. So if only 1 turn is preset, it is rounded down to 0, causing the Pokémon to wake up the next time it moves.
This also applies to the self-induced sleep from Rest, reducing its length from 2 turns to 1 turn asleep (not counting the turn in which Rest is used).