What you are describing is very much like my experiences with my three month old 3800, and the second replacement unit that they sent me (the first one arrived damaged and both replacements have been returned).
The original and second replacement unit both exhibited the overinking you describe. Overly dark blues and cyans, which result in dull greens and poor overall color, regardless of paper. After a couple of months of struggles with this machine, I finally realized that the profiles were unable to compensate for this excessive color error, so here's what I did:
1. I printed the color ramp check print from PrintFixPro (you need some kind of profile generating program to do the complete fix outlined here), and made slider adjustments in the Epson printer driver custom/advanced section to reduce cyan and magenta, with a saturation adjustment to compensate, until I came up with a check print with colors that were closer to the ones onscreen though not perfect (the settings were -10C, -5M, and +10 saturation). I figured that the profiling program would then be able to compensate better for the mismatch than when reading some hard to quantify version of black.
2. I printed the profiling target using the above derived settings, and read the target with the spectro unit. Sure enough, the measured colors looked much closer to the screen view of the target as they were entered.
3. After the profile was generated from this target, the program printed the cleanest test print (the one with the girl, the babies, and the shelf full of familiar objects) I had ever gotten by far, again with the above settings and the new profile.
From this point on with this method, you have to always convert the image to the new profile for that paper, tell Photoshop to let the printer manage color, and print with the same slider settings. Despite the fact that it is not the ideal method of working in Photoshop, it works exceedingly well. A print of Bill Atkinson's test image was a virtual match to the screen. Any differences are extremely minute - finally!
The problem is that the Epson canned profiles produce the same disappointing results that I was getting before coming up with this method. From reading various other posts, I think that other forum members have had similar experiences with the Epson 3800, but were unable to pinpoint the cause. I had ordered a replacement for my first machine because I assumed that it was severely out of calibration. With the second replacement performing identically with no color management, I'm wondering whether that is just the way the units are being set at the factory (I hesitate to use the term "calibrated" as there was no proof of calibration with each machine as there should have been if it were truely individually calibrated).
Aloha, and good luck,
Aaron