I assume your monitor is calibrated, but on mine, in PS6 w/ the PPRGB version, the image looks rather anemic, and improves greatly with levels brought in a bit at both ends.
It sounds as if your soft proof is not matching your prints very well, and I doubt, with the variety of papers you've tried, that the paper is at fault.
Pete