I'm confused as to how this is Coinbase's fault.

The entire point of two factor authentication is that it's impossible for someone to access your account without knowing your password and having access to your code generator. You chose to lose your code generator by getting a new phone without backing it up, AND you removed the phone backup that was provided for you.

This is like getting a new keychain, throwing out your old keys, then getting angry at your bank because you can't get into your safe deposit box.