Respondiendo especificamente al tema de la lineas que ven entre objetos al vectorizar, la solucion es una macro:
http://macromonster.com/index.php?mod=descr&id_desc=27
Jeff's Outline Color Same as Fill
Segundo, respecto a la imagen en sí es verdad que tiene muy mala resolucion, no es necesario usar Photoshop, se le pueden hacer algunos ajustes en CorelDRAW (un pequeño desenfoque gaussiano, ajustar la curva tonal, mejorar el contraste, etc.
Fuera de eso, PowerTRACE no es sólo un botón mágico al cual hacer click y esperar que lo resuelva. Es un programa con muchas opciones, puedes ajustar la suavidad, los detalles, la suavidad de esquinado, la cantidad de colores, agrupar colores por similitud, etc que pueden ayudarte a obtener mejores resultados.
Pero, sobre todo, la gran pregunta como decía Hozé es para qué lo necesitas vectorizar. Si es para usar en plotter de corte seguro que no sirve porque será demasiado complejo. En tal caso, lo mejor sería dibujar los contornos manualmente, sé que parece complicado pero no es muy dificil, y el resultado será sin dudas mucho mejor. Si es para imprimir no necesitas vectorizar.