If what you are printing looks nothing like what is on the screen, the embedded profile in the image and the printer profile most likely do not match. This might be the case since you are using PSE for color management. Regarding your display, if everything else on your screen looks fine (websites, viewing pictures, etc) then your display profile is fine, and would suggest the problem lies with inconsistent profiles between your image and the printer.
Are you just selecting 'print black and white' when you print? Try converting the image to greyscale first (in CS4 it's Image->Mode->Greyscale).
Have you tried not listening to PSE and just allowing your printer to manage colors? Sometimes Adobe software is really dumb and doesn't know what it is doing, especially when it comes to color management.
I'm not sure about PSE, but the print dialogue in CS4 shows you what the current printer profile is currently set as. Make note of what the printer profile is, then find what the profile of the image is (in CS4 it is under Edit->Color Settings).