Regardless of how a vector file is created, it must first be 
converted to a raster image before using in video. I'm sure 
Premiere is trying to rasterize it or use the small embedded 
thumbnail representation somehow.

I believe you said you also own Photoshop? If so, Photoshop will 
rasterize the image beautifully for you. Just import the .ai 
or .eps into Photoshop, it will rasterize the file and then you 
can save it out as a raster image (.tga, etc) from Photoshop. 
Then bring it into your editor. If you want to key the title 
over video, you must create a mask channel and save the file 
out as 32bit.tga.

We do it all the time with client logos that arrive as.EPS files.

Hope this helps.