You cannot do that. The ONLY way you can go from 72 dpi to 300 is if the original is physically huge – say about 24 in X 12 in – and you’re reducing it way down to about 2 in X 1 in. Even with that your chances of getting good print are weak.
The only way to properly do this is to make paths in photoshop and export them to vectors – like Illustrator. Logos are usually quite simple. It is not hard to use the magic wand to make a selection and create a path from that in photoshop. Make as many paths as you need, and export them to Illustrator. Then select the paths and fill in the colors. By default the background is transparent. After that, you can outline the fonts, save as EPS with vectors set to 100%. The thing can then be simp[y made bigger, smaller, whatever with no loss of detail becaue vectors are not resolution dependent.. We do this all the time. It is not hard, nor is it terribly time consuming.
The following web page is an example. The work was ordered at 10AM Thursday and delivered at 10:20 AM. That time frame is average and common. We do this for the client on a very regular basis, fonts outlined if necessary, in eps format It is the logo behind the people.
In this we got a scan of the logo from letterhead in jpeg format, about 1.5 in X 1.5 in black print on white – very common. Opened in PS selected black with magic wand, selected similar, created paths, and exported to Illustrator. In AI select all and fill with some silly color like yellow. Draw a big black box and place it behind the yellow. Then start knocking our all extra yellow fills – like the interior of letters like O or A. When that’s done, change the yellow swatch to white (in this case). For using other colors, simply select whatever you need and fill those selection with appropriate color.
In this case the client requires these things in about 6 in X 6 in. We use Transform to blow it up, save as eps and send it on its way. Again, takes about 20 minutes. As you can see the logo is then blown up bigger and printed.at about 20 in X 20 in. It is also displayed on the outdoor screen at about 8 ft X 8 ft. Since it’s in vectors the size is irrelevant.
In some case the text in the raster is so bad that it's unusable. In that case we simply redo it. In the aforementined example we just used the paths for the interior symbols, exported to AI, and filled. Then just drew a circle and used the type on path tool to recreate the text in the appropriate font. Outline text, save as eps and send to client. It might sound complicated but it is not. Once you get the hang of it, it's very quick.
By the way, any colors visible in the logo on the web page are simply the result of lighting. It is white.
Using OSX 10.3.9 on a G4