I'm not familiar with Premiere (prefer FC and iM), but ANY video edit app I've seen so far, handles audio and video in different tracks, layers, whatever… so, that said, you erase the old music-track and import the new one...
ok, the new version has to be the same length, esp. "keypoints" as any hits, breaks, chorus (whatever structure your piece has) should stay at the same places, because an editor use them as… ehm, keypoints
ok, you all stumble into trouble, if they allready had done some "mix down", by adding additional sound effects, voices, noises, whatever... but a good editor will keep additional stuff on additional layers (e.g. FC offers 99 tracks...) and create final 2c-stereo just at the very end of editing.
but, technical spoken:
earse track, insert track - boom! done...
no "difficult"