I was nikon for over 20 years...ending with the D2x.
I made the switch to a MKIIn and have never regretted looking back, and here is why:
Superior ISO performance..........the 2x was horrible from 800 up
More focus keepers........the focal points are too close on the 2x...many times lost to something behind main subject....creating oof shots (especially on moving targets)
Now back to your question in general about print sizes.......
I currently shoot motorsports.....and sell prints up to 44 x 66 inches that are SHARP!!!!!! and yet the MKIIn is only a 8.3 mp camera......!!?? So why was your images on a MKII soft???
I'm willing to bet........that if you go back and review the images for the following, you'll answer your own question quickly!!
what was your shutter speed to the length of lens used....based on the motion speed of your subject????
Too many times we fail to maintain what I call the Golden Rule of focal length/shutter speed ratio
If your shooting a 300 mm lens....then the minimum shutter speed needs to be 300th of a sec or faster
and if your subject is moving ( and depending at what speed), multiply that by half again.
In doing drag racing....when a car launches off the starting line....while our mind is thinking that its only moving a few feet.......its the power of the launch that succumbs many to soft images. It takes a shutter speed of minimum of 500th of a sec to assure sharp images...but yet the car is only moving a few feet. In doing unlimited hydros doing 160 mph........more the same....shutter speeds up to around 1000th.
SO all that said...........if you have canon lens (and they don't all have to be $$$ L stuff) currently most MKII's are in your price range. IF your only on Nikon glass.......the 2x is now in that range as well....but I'd go for the MKII or MKIIn for sure!!