Recreating the logo in Illustrator is a good way to go... but you can use the Live Trace and Live Paint features in Illustrator to give you a head start.
Save your Photoshop file as a jpg file, then go under the Object menu to "Live Trace" -- adjust your settings to whatever suits your artwork, then "Expand Appearance" to make the art into editable vectors.
Ultimately, what your printer wants is clean artwork based on vectors, you're correct in thinking such a file would come from Illustrator, but since you can now place images into AI files, it really doesn't mean much for a file to merely be an "EPS" file.
For your best success in printing, you not only want this file to be all vector based, but try to avoid stroked lines (go to the "Path" menu, then "Outline Stroke") this will ensure that your line weights scale appropriately no matter what program it gets imported into.
When you do this step, if your logo is simple enough to sort the shapes, make sure you've set an appropriate amount of trapping (overlap of colors) to avoid problems in printing if/when the registration is less than perfect.
And, since we're on the subject of printing success, think about any gradients you have in the file. Depending on how large the logo is going to be used, gradients can create "banding" -- stair steps in value rather than smooth gradients -- if you try to cover too much area with too small of a gradient. There are ways around this... but you have to get away from vectors again.