Are you sure Sparkfun shipped the correct display?
Typically, the displays list the correct operating voltage on the back of the device.
A similar display from Sparkfun, ADM1602K-NSA-FBS/3.3v, it would not be the first time the wrong part was shipped.
Or it could be mislabeled.
P.S.
After examining the product page on Sparkfun, this problem appears to be common issue with the display, review the comments:
Basic 16x2 Character LCD - Amber on Black 3.3V
I've utilized several displays from XIAMEN AMOTEC DISPLAY CO.,LTD, in the ADM1602 series and have not encounter this issue.
Perhaps this is a "bad" batch or mislabeled as previously mentioned.
BigDog