After looking at a few of the backups, I've decided that bitcoind needs a keypoolrefill prior to making the backup.

The default value is 100, but I feel that the code could auto-scale up for large sites if it recorded the number of records that were dumped each time.