The problem might not be strictly shipping related.
Depending on the type of bluetooth radio packaged internally, the device may have needed FCC-type registration. Of course, an FCC ID is only good in the USA. In Europe, you need a CE mark. Australia sometimes insists on yet another registration for 2.4GHz equipment.
Honestly, international RF regulatory certification is a mess, and the piles of paperwork involved make it easy to miss deadlines.