If you want to know why exactly this happens, regardless of whether or not it has affected you, this post will at least show you how to avoid falling victim to this security measure again if you find it to be too much trouble, as well as why this feature exists to begin with.

Why am I locked out of my phone for 72 hours?

Back in March 2015, Google introduced a feature called Device Protection in its newly-released version of Android, 5.1 Lollipop. Part of this new suite of security tools was something calledFactory Reset Protection. This is the source of the 72-hour device lockout. It is tripped by resetting your Google account password and then performing a factory reset on an Android device (with Device Protection, meaning it runs 5.1+) that account is connected to.
This feature is designed to allow you time to regain control of your Google account in the event it is compromised because your phone was stolen. Think of it this way: if somebody changes the lock on a security door (your phone) the night before the building gets robbed, do you think the person changing the lock (or someone else at the lock company) might have been in on it? That's essentially the logic of factory reset protection. The idea is that your Google account and password are the "lock" and "key" that are required to open your Factory Reset Protection-enabled device (the door) after it undergoes a factory reset, and that by changing your Google account password, you're "tampering" with the lock right before you enter the door - which is suspicious. And so at that point, Google initiates a 72-hour hold on sign-ins to that "door."
After that 72 hours expires, you still need to log in with the previously-connected Google account's password. The difference is that during the hold, you just can't log in at all - after the hold is over, you obviously still need to verify the account password.

Why is this a feature? Isn't this insane overkill?

The reason the hold is triggered is that, once your Google account is compromised on a stolen phone (easy enough to do - the thief has your Gmail and probably your phone number), there is essentially no other way to stop a thief from successfully erasing all traces of your account ever having been on said phone, since a wipe can be done directly from the recovery menu on bootup without any sort of authorization (PIN/pattern protected startup does not prevent this). That 72 hours theoretically gives you time to get your Google account back under your control and change the password again, making the thief's attempts to log in futile.
If you're wondering why a thief would know your Google account password and not your PIN/pattern lock, that's actually more likely to happen than you might think: it's completely possible to reset your Google account password without knowing the current one if you've got somebody's smartphone. Two-factor authentication generally relies on SMS, so the thief would get the authenticator on your stolen phone, and you probably would also have your backup email account synced to that smartphone as well (which, hey, good personal security idea: don't put your backup account on your phone).
Generally speaking, it is comparatively much, much harder to change the lock screen on a phone if you don't know the existing PIN, pattern, or password, and short of social engineering or plain luck, that's hard information to get.

Is there any way around factory reset protection once it's triggered?

Sadly, no. Once the protection system is tripped, you've got a functionally useless smartphone until that 3-day lockout expires. If you've been locked out of your device and are looking for a workaround, sorry: there isn't one that we're aware of. You're going to have to wait (you also cannot sign in to the phone using another account - this would kind of defeat the purpose of the feature).
Those affected by this problem have confirmed Google support is of no help in the matter - they'll just tell you to wait out the timer, during which time your phone has all the utility of a paperweight. This suggests Google really has no control over the timer itself once it's been triggered, though we can't be sure.

Can I disable this feature (Factory Reset Protection / Device Protection)?

Nice try, phone thieves! But really, in the interest of full disclosure, yes - you can disable all Device Protection features (and it is an all-or-nothing switch), including Factory Reset Protection, and doing so is relatively quick and painless on supported devices. Here is the process.
  • Enable developer options on your phone (Google it - it's easy, usually you just go into the settings, "about phone," find the build number (might be under software), and then tap it until it says "You are now a Developer!")
  • Go to developer options and find "Enable OEM unlock."
  • Check the box, and hit "enable." You will get a warning saying this will disable device protection features, and this includes factory reset protection. And I've tested it - factory reset protection no longer works with this checkbox enabled.
If your device does not have an "allow OEM unlocking" option, that means one of two things. First, it most likely means it doesn't support factory reset protection to begin with, and that your phone is not protected in the event someone wipes it (or it may have a 3rd party solution!). Second, it could just mean the company that made your phone (or the carrier) decided not to include the OEM unlock toggle and is kind of a dick, and in that case, you only have one option, and it's a bad one (bottom of this section).
As to what "allowing OEM unlocking" really does, it basically tells the system that the bootloader is authorized to be unlocked (note: not the same as actually unlocking it) and that Android won't stop you in the event you should attempt to do it. And yes, this makes your phone less secure, because it potentially means a thief could flash custom software to your phone, etc., and Google is politely saying it's not their problem if something bad happens when you do this.
If you don't want to use the Enable OEM Unlock method or do not have such a toggle, the only other practical option to disable ADP is to run with an unsecured lock screen. Not very appealing, right? Android Device Protection requires that you have a PIN, pattern, or password for your lockscreen in order to function. Without those things, its features become useless anyway - accounts can be removed from the device without any additional authorization, and thus there's really no protection to begin with.

How do I know if my phone has Factory Reset Protection?

The easiest way is to just do a factory reset (while logged in to the device with a Google account and a screen PIN/pattern set) and see if you get the following dialog on startup.
If you do, you've got factory reset protection. If you don't, you either don't have it or it's disabled.
Device Protection should be on almost any Android device that shipped with Android 5.1 or higher out of the box. It will also work on some phones that shipped with some version of 5.0 (5.0, 5.0.1, 5.0.2), such as the Galaxy S6, and were later updated to Android 5.1 or higher.

Is there any warning about this when I factory reset my phone?

Nope... which seems really bad on Google's part, if I'm honest. Devices should clearly state as part of the factory reset dialogue that they will be completely locked and rendered unusable if you've changed your Google password in the last 72 hours. Does this let phone thieves know how the system works? Certainly, but it still accomplishes the purpose (prevents a wipe), and it would bemuch better for end users. People have already encountered this feature unwittingly after resetting their Google account passwords, only to be locked out of their only phone for 3 days with absolutely no way to resolve the issue - and these people did nothing wrong. It's totally ridiculous that this is how it works, and Google should most definitely address it.
So, the lesson? In the event you change your Google account password, you must wait three days before factory resetting any of your Android 5.1+ devices you use with that account unless you have explicitly disabled Android Device Protection on them. If you factory reset one of your Android devices before that 3 days are up and then attempt to sign into that device with your Google account, you will be met with an error message and not allowed to log into the device with any account until 72 hours after the password reset occurred, which is a major bummer.