That may be a problem with the current implementation, but it doesn't have to be. There's no reason your credit card couldn't be e.g. loaded onto your phone, using NFC to talk to a reader, and then it could be updated instantly if need be.
> I had to re-set up all the bills I had set up to be automatically paid with the previous card to now be paid by the new card, etc.
The only reason this isn't a problem for Bitcoin is that you can't set up bill payments in Bitcoin at all.
> Still, some fraud scenarios are completely eliminated with Bitcoin. I pay a fraudulent restaurant with a CC that gets skimmed, I get to deal with the hassles of having to have the card replaced, potentially having my credit score damaged, etc. I pay a fraudulent restaurant with bitcoins, I know the restaurant can do nothing to steal the bitcoins remaining in my wallet.
It works for a restaurant but that's a very special case - you pay after you already know that what you got was right. More often you're buying something where you won't realise if it's broken until you get it home, in which case much more serious fraud is possible with bitcoin than with credit cards. And even the restaurant case is not a compelling advantage for bitcoin - if your credit card gets skimmed the worst case is really not very bad.
> Private keys can be very well protected and almost impossible to steal
Sure. But the kind of person who gets their credit card PIN stolen (which is what we were comparing to) isn't going to have a well-protected private key.
> Every day, millions of Americans use financial instruments that are not FDIC insured
Sure. But almost everyone gets an FDIC-insured account as a backstop before getting any of those other instruments. And it's convenient to have all your accounts in the same currency.