I think it's not really quite as cut and dried as that - it can also depend on the level of detail in the photo (lots of very fine detail may not scale up as well), how it's going to be viewed (e.g. in a large room versus up close in a hallway), and of course how sharp the shot is to begin with (meaning how much actual resolution is in the photo versus the sensor's resolution).
When I was shooting with my D70, which has a 6MP sensor, I printed a number of my photos at 8"x12" with good results. I probably could have gone a bit larger than that.