I'm a big fan of Tim Ferriss and I tried Total Immersion swimming after his recommendation. I've had similar experiences to you, MartinP. Breathing is still the hardest part for me, but I find it gets easier with practice and just the familiarity of being in the water.
The main problem I've identified with my breathing is that I don't breathe out properly with my head in the water (I either do it too fast or not in one continuous exhale), and then I'm gasping when I turn to take a breath. I've taken to practicing at the side of the pool, just dipping my head in the water and trying to do one calm, continuous exhale, then turning my head to the side and taking a quick breath before going under again. I've gotten more used to the technique but I still have a ways to go. I believe the main trick though is just learning to relax completely in the water.
I'd recommend you register at the Total Immersion site (
Welcome to Total Immersion) to get some free PDF guides. I found those helpful.
And don't get discouraged if you can't see results as fast as Tim. Not many people can ;-)