Live Trace may give you something useable but it is quite crude in what it creates.
Are there any paths in the Photoshop document you can copy and paste into Illustrator to speed up the redraw ?
does it vectorize it if u just rag the psd file form the desktop into illustartor?