Hola..
Se te pixela al achicarlo? eso es raro.
Posiblemente se vea mal al achicar el Zoom, eso es normal, pero al achicarlo realmente no tendría que pasar. Pero respondiendo a tu pregunta, hasta donde sé el Photoshop no vectoriza, para eso Adobe tiene otro producto y se llama Streamline <a href='ir.asp?http://www.adobe.es/products/streamline/main.html' target='_blank'>http://www.adobe.es/products/streamline/...</a>, tambien tenés uno de Corel, el CorelTRACE (<a href='ir.asp?http://www.es.corel.com/PRODUCTS/draw10.html' target='_blank'>http://www.es.corel.com/PRODUCTS/draw10....</a>), pero viene con la suite del CorelDraw 10 (no es aparte).
Yo te aconsejaría redibujar el logo en Illustrator ó Freehand para manejarlo a tu antojo.
Saludos y suerte...