There is a simple reason it's a mess..
Europe is trying to fix a mess that is not of its own making.
The problem is that the US has wandered too far into a modus operandi that has all the trappings of a police state in that there is very little control over agencies and law enforcement accessing information. Add to that the issues that Snowden laid bare (basically, agencies happily overstepping the few remaining limitations set on them, and God help whoever dares blowing the whistle on that) plus the fact that open, unrestricted access means lots of money for the likes of Facebook, Google and friends and you have a mess that is only fixable from the US side of the border. Where there is ZERO interest in doing so, unless it costs someone money or campaign contributions.
This is why it is so difficult to come to an agreement - Europe is trying to impose a much better privacy regime on a country that is hell bent on not learning the lessons we already picked up during our history. I'm not sure where this will end, but I suspect lots of bribing lobbying may be in progress, with the European side simply holding out for better payment agreements. I am as yet unconvinced any of that haggling is actually in our interest - only the results will tell.
It is not exactly helping that actual government bodies seem to have no problem with breaking sovereign secrecy. Important bits of UK government like Cabinet Office happily use Gmail, which once upon a time would have been cause for CESG to storm in and rip the civil servants' computers out of their coffee stained hands, but security no longer seems to matter. Weird.