Are you sure you're viewing your "too dark" prints under a good enough light? If you're looking at them under your overall room lighting, then it's no surprise that they appear too dark. Put them under gallery-type display lighting, or in direct bright sunlight, or any other bright light, and see if they still appear too dark.
(I speak from experience - I could have written exactly your post a couple of years ago before I happened to look at a "too dark" print of mine under better lighting, and found that it suddenly matched the monitor muuuuch better.)
The printer profiles assume that the print will be viewed under optimal display lighting, not whatever lighting happens to be near your computer.
Lisa