absolutely no offense to pixel as he/she seems pretty knowledgeable but i have re-done several logo re-draws over the past few years and since illustratorCS2 came out with the 'live trace' option, it makes things significantly easier.
if you do not have illustrator, drop by adobe.com and download the trial version. open a new document then go to edit>place, and choose your image. select your logo/image on the 'canvas' and the top bar will give you the option of 'live trace'. there are several options to choose from as well as custom settings to create on your own. live trace has saved me HOURS as i no longer have to trace/re-draw everything with the pen in illustrator.
the advantage of using live trace in illustrator is that the finished product will be a vector image, not raster. you probably know this, but for those who don't, vector images never get, uh, 'pixelated'. they can be resized from small to large or large to small how ever often you wish with no unpleasant repercussions in the form of a low quality, generically resized .jpg
on a side note, i used to work in a print shop and know that the printers will adore you for sending them a easily editable (color-wise) vector (like an .ai, .eps, or certain types of .pdf) originally created in illustrator. it would take the concern of DPI (dots per inch) out of the equation altogether for the reasons stated above. also, if you feel kind of weary about going into illustrator without much experience, don't worry; its pretty straight forward and there are hundreds, if not thousands, of free tutorials available via google on how to use the live trace option.
have a nice one and i hope this helps. if you still have problems, well, i have some spare time. send it my way and ill see what i can do.