Saving a png file as a vector pdf

Further to the above excellent advice, your PNG file can be converted to a vector image using the tracing capabilities of programs such as Adobe Illustrator, Corel Draw or the very good free program Inkscape.

There's some advice here:
http://graphicssoft.about.com/od/bitmaptovector/Bitmap_to_Vector_Conversion_Tracing_Software_Raster_to_Vector.htm

I'm afraid that I have to take exception to the suggestion that vallis has made about using the tracing capabilities of software programs to generate vector images.
The tracing algorithms used by these programs tends to round out edges and obscure detail.
The programs work well on images that are high enough in resolution that such a loss is acceptable, or for use where a degree of loss of detail is expected. (many years ago, I picked up freelance work converting artwork into vector images that were used to etch designs into tomb stones. no one expected a design sand blasted deep into granite to have a high degree of detail)
The suggestion here is that the printer didn't find the resolution that he needed in the png. If this is the case, such an image would be a very poor candidate for using an auto-trace program.

What cost you to try some free online converters?
http://vectormagic.com/home
http://www.fileformat.info/convert/image/svg2raster.htm
http://www.tlhiv.org/rast2vec/
http://image.online-convert.com/convert-to-svg
http://www.converthub.com/

I will upload a copy of the png here (later today), so that we can see if it will be a workable image. I'm also contacting the logo designer in case we are not and she can create the png.

Please upload the logo so we can see if it can be recreated fairly easy. I recreate all logos in Illustrator so i dont run into these issues. But of course it depends on your logo.

Some people have an image as their icon instead of vector based art.

If you have good contact to the logo designer then this is the best option, I am in agreement with D_Brugge's assessment that any conversion is usually inferior and may lose detail unless the PNG is of good enough quality.

hth
capt.

Here's the logo.

I do have a good enough relationship with the designer to ask for the file in the right format, but also want to learn what to do (perhaps always just keep things in the original format?) for the future to avoid this issue.

Helps if I attach things properly, eh?
3--80.png

I used vectormagic site 2 min time
3--80.pdf

There is also a stand alone free software as Potrace:
http://potrace.sourceforge.net/#downloading
http://potrace.sourceforge.net/samples.html
After you download you need to run at command prompt the execution of the conversion.
You copy the folder with Potrace (after unzip) in C:\ for example.
Then in folder you copy your file as bmp - so you have to open first Paint program from Windows , open png file and save as bmp
Then in command prompt (Just go in Windows at Run and write Cmd) you have to find the folder where is Potrace. For example use "cd.." to go back to C:\ and then write "cd C:\potrace"
When you are in command prompt at C:\potrace then you write next command
"potrace -b pdf 3--80.bmp"
of course 3--80.bmp will be each time another file
for more help you have to read th usage on internet or read files or just type potrace -h at command prompt
I just played 15 min with this program, is not perfect but not bad.
See the result attached.
3--80-v2.pdf

Here is better version for you, but you have to learn.
The software is free and is specialized for vectors. It is called Inkscape.
http://inkscape.org/
http://sourceforge.net/projects/inkscape/files/
After you download and install you can look at some tutorials even on youtube:
http://www.youtube.com/watch?v=mlsf3f_YI6s 
http://www.youtube.com/watch?v=bSR_dI1gE4E
or just read the help:
http://inkscape.org/doc/tracing/tutorial-tracing.html 
http://tavmjong.free.fr/INKSCAPE/MANUAL/html/index.html 

In simple steps and words:
-      After you install and run Inkscape, just open your png file (embedded), then keep Shift pressed and with the mouse select the entire file.
-      Then you go in menu up to Path\Trace Bitmap then you choose Colors, Smooth, Stack Scans,…then Update and OK
-      Then you just go File Save As; then you choose pdf and ready.
You have to play with the parameters from that windows Trace Bitmap to obtain better results.
A very nice result is when you do it “manually” as you can see in the youtube videos (you may search more tutorials)

Attached here is the result of 3-5 min playing with the software.
3--80-v3.pdf

Agreed, I did try the online converter, and while it did seem to take some of the pixelation out of the edges the printer still said it wouldn't work. I'm waiting for the response from the designer now, as that seems to be the only option.

Thanks so much for all the input. I learned a lot, including the fact, that sadly, this cannot be done to satisfaction from a png.

Thanks for the accept and to D_Brugge for the technical explanation. Print requires the correct setup and is not as forgiving as on-screen design, so there are some key prerequisites to observe even after digital publishing makes it all the more straight forward.

Please do return if you have any other question, we are happy to help

best wishes
capt.