Not surprising since it's been a while since you've experienced the issue, it's just given enough time to work.

If that happened again and you're in a hurry, you can try to set a "fallbackfee" so its value will be set instead if the estimate isn't available yet.
Set it to your bitcoin.conf file like: fallbackfee=0.0001
The value's unit is in "BTC/kB".