also, make sure that the paper is appropriate for your printer. I've found different types of docs print differently on the same type of paper.
On one type of paper, the type was incredibly sharp, but other colours bled, probably the same as your case (even though I checked all appropriate settings), whereas on another type of paper, the text bled but the photographic elements were much crisper.
Since you seem to be fairly new to this, I'd also ensure that your document is in CMYK mode (go to Image>Mode>CMYK) and set at 300ppi. Change this through Image>Image size. Make sure resample is NOT checked, and set the resolution to 300. If the image is too small to begin with, this probably won't do you much good, but it's important to know if you want to get quality prints.