You might try by going back to the original and changing the resolution first. I don't think that will solve the problem altogether.
The OP did say that he started with vector art, so, it's possible that he started with an AI file that he imported into PS. If this is the case, then increasing the pixel dimensions of the canvas before import would completely solve his problem. Unfortunately, my guess is that the components he started with were called "vector art" by someone else, but, in fact, were really only JPGs or some other type of bitmap.
Another option is to have the design redone with a pen tool. But first increase the resolution of the document.
I don't think he's going to like all the work implied by that suggestion.
A third option is to get a plugin which will enhance the enlargement process.
I own the current incarnation of Genuine Fractals (aka, onOne's Perfect Resize) and, over the years, have experimented extensively with other plugins and up-rez'ing methods. In my experience, he isn't going to be happy going from his current 1600x800 to something having many times those dimensions. One usually can up-rez by 2x in both dimensions without incurring too many problems (see attached), but beyond that, it gets dicey.
The only saving grace is that because posters are typically not subjected to pixel peeping scrutiny from a few inches away, he probably will be able to get away with surprisingly low ppi values, so the required enlargement in pixel dimensions may not be as great as he thinks he needs.
If he doubles both pixel dimensions (as per the attached files), he'll be able to go up to just under 2 feet by 4 feet without it looking too bad (ie, 72 dpi). If he needs to go to a 4 foot by 8 foot poster, he could use the same 3200px by 1600px file (at 36 dpi) so long nobody is going to be able to get closer than a few feet of the poster.
The two attached files are versions of his 1600x800 image up-rez'ed to 3200x1600. One was done using Genuine Fractals / onOne Perfect Resize, while the other was done using Topaz Vivacity's special 2x-only resizer.
HTH,
Tom M
PS - Under no circumstances should you judge the quality of the up-rez'ed versions by simply viewing the preview versions displayed in-line in this thread. This forum highly compresses these previews. Instead, download each and evaluate them in Photoshop or some other competent file viewing software.