If you're going to print big, you'll be better served with higher MP count. Do keep in mind, though, that resolving a 12mp APS-C sensor does take a heftier lens than resolving a 4mp APS-C sensor. In many situations, you're not getting the 12 mp of ie. a D90, because of issues like diffraction or just general softness with large apertures. Printed at the same size, the 12mp camera will surtainly have the advantage, there is a lot more information in it, but then again, that's to be expected. Don't expect though the same pixel level quality with the same settings on most lenses on both cameras.
But as with most issues, your milage may vary, some need higher resolution, some really don't. I've been living with 10 mp for the last 3 years, and can't say I've ever really wanted more. Couple of months ago I reviewed Sony's a850, and I kept getting irritated over the senseless amount of pixels I just didn't need - or for that matter, wanted.
That's me. It may not be you. But as long as I tell you why I don't need the higher resolution, I really don't think it's any of anyones business that I say that a given res is good enough for me.
Wanna print billboards? Okay, given that you do, and that's suprising as that market's almost gone down the drain, but given you do, you can almost surtainly afford a camera to fit the job, and I'm quite sure you're not using an APS-C dSLR, you'll probably want a digital medium format back for that.
Just my .2