Hi
just joined because I've been getting this problem too, and this the only place a google search turned anything up - can't help with the prob, as have only been using LR for a few months - but at least we can both feel no longer alone with it !
I mostly use the contact sheet for scanned 36exp film work as part of my degree course - unlike the OP, my missing image [usually only one in a 4x9 sheet] is part-way through, rather than first.
Happens with actual prints and print to PDF via PrimoPDF - but if I print the same sheet in 2 consecutive LR sessions, it's not always the same image !
[Not tried print-to-jpg, yet]
Getting a bit frustrating now as I have to submit these sheets for assesment - if I can't resolve it guess I'll have to use CS4.
Cheers
IDM