something like perfect resize by onOne will do a better job than photoshop. Also some believe that blowing them up incrementally by 15% will produce a better result than going straight to your final print size, but i've never actually tested this.
if you don't want to tell with it at all, there are also some pro labs that will do the resize for you. Just saw one the other day, I could probably find it again if you wanted it.
wow. yeah i was just going to blow it up in photoshop and hope for the best. pretty glad i asked the follow up question. i think i'll just play around with Perfect Resize, trying to keep the budget low on this. thanks.