La incógnita es que si el logo lo hiciste en Photoshop desde un principio...si es así la mala noticia es que lo vas a tener que recrear nuevamente en Illustrator
Existe una forma de convertir archivos de Photoshop a Illustrator mediante "Live Trace", pero sale medio feito y es mejor volverlo a recrear enteramente el logo que tratar de arreglar el archivo de Photoshop mediante Live Trace,
Si el logo esta hecho en Illustrator no importa el tamaño en que lo hagas ya que un archivo vectorial no pierde calidad si lo haces chico y luego lo agrandas, pero es todo lo contrario con un JPEG, TIFF o incluso un PDF.
Así que por regla general, cuando mando un logo que fue creado en Illustrator como .AI, lo que hago es hacerlo al tamaño de una hoja carta—grandote— y luego lo salvo como EPS ahí mismo en Illustrator y los demás formatos los hago en Photoshop, abriendo el archivo .AI o .EPS y así como Valentina mencionó, los convierto en JPEG, TIFF y PDF en alta resolución a 300 dpi y en CMYK.
Ojo, el archivo de Illustrator lo tienes que convertir en CMYK primero antes de hacer todo lo anterior...
Espero que te sirvan estos consejos.
Saludos,
Sergio