I had the same problem trying to print the labels with my HP 895 printer. Nothing I did would force the labels to print right. However, I did solve the problem. Here's what I did.
I displayed the PDF file of the labels on my computer monitor as they are supplied by BookCrossing. I then used a screen capture program called HyperSnap (http://www.hyperionics.com/) to capture just one of the labels. Any screen capture utility will perform this function. The captured label was saved as a GIF file.
Next I opened Microsoft Word XP and opened a blank document. I then clicked on TOOLS and LETTERS & MAILINGS and ENVELOPES & LABELS. I clicked on OPTIONS and changed the lable size to 5163 and clicked OK. Next, I Clicked on NEW DOCUMENT. Word then opened a window with the outline of the label page. Next I went to INSERT and PICTURE and browsed to my saved GIF file and inserted it. I then copied and pasted the label into each of the label outlines and printed the labels. Everything worked adequately.
I thought the gray type on the labels was a little light to I opend the GIF file in an Image processing program called Ulead PhotoImpact (http://www.ulead.com) and bumped up the contrast a little. The next set of labels were as good as printing from the PDF file.
What BookCrossing needs to do is provide a single label in an Adobe PhotoShop format or Ulead PhotoImpact format so that we can create our on pages. Another alternative would be to provide the labels in Word format.
I know that my solution may sound complex, but that's only because I spelled out the steps carefully. It actually only took me about 10 minutes to figure out and follow the steps I described. It should take you less time because you have instructions to work from.