Not all 8 megapixel cameras are created equal. What is the actual resolution of a photo? Express the answer as x pixels wide by y pixels tall.
It depends on the printer too. If the printer prints at 300 DPI in both directions, then you can divide x and y by 300 to get the size in inches. If the printer prints at 150 DPI, then divide by 150 instead of 300.
The stores that do enlargements have charts of the file sizes required for good results. At one store, I was told that for 36" X 24" you need at least 5400 X 4200 pixels.
I have done 16x20 with ease using a 30D ( 8 megapixel ).
Some of these even came from indoor basketball which we know
can be difficult do to higher ISO's required. Like others have said,
less noise would be better. I would also try to match the print company's
DPI when prepping your file for upload.
I blew up a 20" x 30" picture of my daughter taken with a 6.1 Megapixel Nikon D40 and it was flawless. I have in the past blown up an 8.5 x 10 from a 12 Megapixel point and shoot that I threw directly into the trash. Numbers really are only numbers. I'd blow it up and see if it makes you happy.
Most posters are printed at 150 dpi (to save on cost) 300 is ideal. Do the reverse math. Below 150 dpi will start to show pixelization, which you can see if you are right on top of it, but if you stand back 5 feet it is fine. A publisher I work with like to have at least 10mp for his magazine. It is really up to you on how clean you want it to look.
Sorry, but there's no simple numeric answer to your question that will be true in all cases. I feel subject matter and image characteristics to be even more influential in this decision than pixel count - I have printed murals that look sharp from small files, and small prints that look soft from huge ones. Also consider that the ANGULAR size of all prints is about the same since the proper viewing distance increases proportionally with print size, so the perceived pixel size will also be the same. A good RIP will upsize the image on its way to print quite successfully within limits, so pixels won't really be a problem until long after sharpness has taken a dive, if at all.
So, if your small print looks good up close, try it larger and see how it holds up. Good luck!
As everyone else has said, we'd need a lot more info, and in the end it can be a matter of opinion. I have made a few 20"x30" prints from my 8mp Canon 20D, and I think they look pretty good. The subject was landscapes with lots of fine details and smooth gradients. I shot at ISO 100, and used a tripod.