A3 size at 300 ppi is 4961x3508, so the image fits perfectly. The problem needs to be somewhere else. Even if they put it in A3 portrait, the resolution of the picture should still be good enough. You will need exactly how they came to the conclusion, that the resolution was not good enough, before changing what needs to be changed.
You can upscale the image carefully in Photoshop, but I doubt that you will see a substantial improvement on the print.
Edit: if there is a quality issue with the picture (check it on screen at 100%), then for sure, it is not adapted for the intended use.