Law STUDENT here.  STUDENT, not lawyer.  This is NOT LEGAL ADVICE.  This is simply what I would do if I were being f'd around like you guys apparently are.

Don't hesitate.  File complaints with your state's Attorney's General.  Follow up with a demand letter.  Give them 30 days to resolve the matter.  Print out the emails that you received from coinbase indicating that it was their problem.  Go in to your bank/credit union's branch manager.  Show him/her said emails.  Beg them to refund the NSF fees in the mean time.  PROMPTLY file a small claims court civil action for all of your losses and add $1,000 for negligent infliction of emotional distress.  You will not likely get the $1,000 but you will likely get their attention and your fees reimbursed.

Good luck.