Priority queueing is not necessarily the culprit here. You will need to be sure that your carrier has QOS & COS enabled across the network between both endpoints. If one end does not have it, both ends can suffer packet loss as you describe.
Priority queueing just says which packets get to leave first. QOS says how much of the pipe can be used for which different traffic types. COS says what the traffic type is– whether it is realtime, like voice, or other .