You don't need to resize the image in pixels to change the DPI, this is exactly why I find the requirement for a 300 DPI image from printers to be quite frankly stupid without them also providing a size in either inches or pixels it has to be.
Let me explain again, if you take a screenshot of your monitor the image is going to be either 72dpi or 96dpi. For arguments sake lets say its 100dpi. If you go to print this image by default it will print at 16in.X12in. The width is 1600, divided by 100 you have 16 which is where the 16 inches comes from. The printer(your computer printer) is going to print 100 x100 pixels in a square inch.*
If you set the DPI to 300 its still a 1600x1200 image but now we are dividing by 300. By default it will now print at 5.3in. X 4in. The actual pixel size of the image has not changed, you've only changed the default scale that it prints at.
The other way to look at it is DPI is a translator, it acts as the middleman between the digital world which uses pixels as a measurement and a physical size in inches the image is printed at. Again, a requirement for a 300dpi image without a requirement for inches is really useless. Without that information they are going to have to resample your image anyway.
I'll give you another perspective going the other way, suppose you scan a 6X4 photo at 300DPI, the resultant image is going to be 1800X1200.
*note that these are defaults, printing software or applications can resample too and change the DPI or size of the image on its own...
As far as the quality goes make sure you are using a good image application, secondly use bi-cubic as the method for resizing. However you're going to be creating a larger fuzzy/softer image if you're scaling up.
They do have have plug-ins for photoshop and other applications specifically for scaling up, genuine fractals is one. These plug-ins examine the image for edges of contrasting color, it preserves them which will avoid the fuzziness.
I don't use them because I'm too cheap :P I scale in small steps using a program called neat image to clean out the softness. Works nearly as well but a lot more work.