You can always try some resizing plug-ins like Genuine Fractals or Perfect Resize. Using PS' own stuff may work if this is merely a street poster and doesn't require perfect sharpness... A bit of sharpening and tweaking colors may do the trick then...
Type Layers and Vector Masks should upscale »perfectly« anyway.
Is recreating the poster at the proper resolution no option?
Depends on the content.
If you've created vector objects, e.g., shapes, it won't lose anything.
Photoshop can upsample photo imagery pretty well nowadays too, using the Detail Preserving option in the Image Size function.
But why ask? Choose Image - Image Size, and see how the result looks for yourself.
It's a a "collage" of photos, not vector objects so upscaling would definitely screw things up a bit. It have 3D objects layed on top of it, which do obviously upscale just fine, it's the photographs in the background that prove to be an issue.
I had a friend print me an internet JPEG of one of my other projects (72 DPI) from Vistaprint on a 24x36 and it looks decent.
So should I continue at 72 PPI? Or start all over at 300 PPI?
Here is a little tidbit at 100%:
Yes--the photo is certainly not the best but as is stands and I am OK with it's quality. (Forgot to lower my ISO when I shot it) This project is just for a friend and not a client or anything. But I fear that any more upscaling will just put it "over the edge" in terms of overall quality.