I've had this before too. I haven't tested for a few versions, but I know that evince was unable to open USPS shipping labels, and I had to go install Acrobat Reader for Linux on my parents' computers. :(
I've had the same problem using Preview. While recent versions of Preview might open the USPS labels, they did not render as well as they did in Acrobat. An earlier version of Preview did a better job of rendering.