By itself, the DPI number that's embedded in the metadata of the file isn't a real number. It's not something measurable, it's just computed based on the original image and the desired print size. Unless you are going to print, it's meaningless. How many inches are in a file that's sitting on your hard drive?
The two REAL things that matter are:
1) The size (in inches) of the desired print
2) The pixel dimension of the image file.
The DPI is calculated based on those two; OR, often you use the DPI to calculate the pixel dimension that you need for a particular print size. But it's still an imaginary number.
A file that's 2400x3000px that says "300DPI" in the metadata is exactly the same as a file that's 2400x3000px that says "72DPI." That embedded metadata is absolutely meaningless. If you print that file at 8x10, you printed it at 300DPI. If you print it 16x20, you printed at 150DPI. If you print it 4 feet by 5 feet, you printed it at 25DPI. A print service that demands that the embedded metadata say "300DPI" doesn't know what they're doing, and I would find a new print service.
Having said that:
If you're resizing the file in Photoshop to a desired size IN INCHES, and you're letting Photoshop calculate the new pixel dimension based on 72DPI, then you've got files with the wrong pixel dimension.
If you told Photoshop that you wanted 8x10 at 72DPI, it would make you a file that's 576x720. That PIXEL DIMENSION is too small to get a nice print at 8x10 INCHES, regardless of what you embed in the DPI field. If you change the DPI field to 300, and the pixel dimension is 576x720, you still can't print it at 8x10. If I get one of those "Hello My Name Is" stickers, and write "Hulk Hogan" on it, it won't change me into Hulk Hogan when I stick it to my shirt. (I tried, it doesn't work)
If you sent the print service a file that's 576x720 and asked them to print it at 8x10, then they are correct to reject it, regardless of what's embedded in the DPI field of the metadata of the file.
So:
1) Figure out what size in inches you want to print
2) Figure out what pixel dimension you need for that size print
Calculate number 2 based on the printer's required DPI for the print medium. Generally this will be 300 but might be much less if you have a large or forgiving print medium. You can get away with 150dpi or maybe even 100dpi when printing on canvas. You can get away with 20DPI when printing a billboard.
If you RESIZED the pixel dimension of your original files, using 72DPI to calculate the final pixel dimension, then yes you need to re-work them. However, if your files are still the original pixel dimension as they came out of the camera, and they just say "72DPI" in the DPI field, then you don't need to re-work them, you need to find a new printer.