Sounds to me the problem is your original file started as 72 dots per inch resolution. You can't just increase the resolution to 300DPI and expect PS to create beautifully sharp printable images. Going the other way sure. (but the smart kids out there will know to "Convert to a Smart Image" before they go scaling up and down.)
On Screen it looks fine because your screen is 72 dpi.
However if you've got a 72 dpi image and a 300 dpi image both at say one inch, and you zoom in you should notice the pixelation on screen.
The other issue, might be that your export pdf settings are low. Creates smaller pdfs, but for high quality prints 300dpi is a good minimum. Firey Printers near photographic at 1200dpi. Professional printers should start griping if you send them files below 150dpi.