High resolution images for large posters in Photoshop

Hello everyone!

I am trying to have some posters created (roughly 40 cm x 60 cm).  The images I have submitted to the company have rejected them and said the quality of the resolution is very poor so I am back to square one.

Is it possible to get an image and then make it into high resolution for printing?

The 2.0 Upscale facility within Photoshop CC has been recommended but when used does not seem to help.   The images I am currently working with are around 1000 px plus and 72 dpi initially (before increasing to 300 dpi).

Could anyone please enlighten me on this subject?

Thank you very much!

Message was edited by: Sahil Chawla