@Nathan > thanks for coming to the forums. It's much easier to provide support here with no 140 character limitation!
First of all, are your CDJs on the latest firmware?
Secondly, what software do you use to burn CDs / where do you download your music from? Have you embedded artwork?
Can you reproduce the problem consistently? Perhaps the error occurs with the disc rather than the CDJ...?