Are you running Linux on bare metal or in a virtual system?
As I wrote, I have seen this behavior a lot in virtual environments. On bare metal I would try to use another cable as a first try.
It looks like, that the core SAM-BA connection is more timing critical then the 16U2 programming port connection.