Your experiences sound very similar to mine (though on a much more professional scale - fortunatly I just dabble in these things).
A recent visit to a local pro-lab showed that while they had a practical colour management system in place, they had little understanding of it, and their workflow was far from optimal. Most questions or sugguestions were met with "thats what the machine does, and we work with what comes out".
My dealings with a MAJOR international publisher weren't much better - upon asking about gamma and/or colour space I was met with blank looks from the production staff. Their solution was for me to keep sending them adjusted images, and they sent proofs back until it looked right.
As it's your reputation on the line, and YOU want it to look right, all I can sugguest is you keep working with them (and be greatfull they're happy to keep working at it) until it looks right.