I plugged mine in and sent four new books to it through Calibre. They all four show up on the "Recently Added" line. Disconnected, played with it a bit, then reconnected and added one more book. It showed up as a new book in the "Recently Added" line on the left, pushing the other new books over one.
This was in Main Memory, and with about 700mb left on the device. Are you sure you're "Eject this Device" to unplug it, and not just pulling the cable out?