I had a similar problem after a failed sync a while back. Every time I'd boot the player it would rebuild the database. It was taking over a minute I believe. A proper sync and rebuild with emplode fixed it.

Bruno