If I were you, I'd start by printing out the parameters for the label type you're using. It looks as though some measurement may be off by a tiny bit. The data are in
@PDF::Labels:PageFormats. Then I'd check the measurements (multiplying small ones by the number of labels across or down the page so any possible mistakes could be more easily discovered). You might also want to ensure that you are printing USLetter labels on USLetter forms or A4 on A4. You might also be able to verify the data if you have a copy of MSWord, MSPublisher, WordPerfect or some other package that knows labels.
HTH, --traveler