It could be that it is related to Coinbase's server and not you personally. If you want to know that it isn't your fault for sure, and since you have 2 phones, try to forward the clock on your first phone with 30 seconds, and make the clock on your other phone go back in time 30 seconds.
Thanks. I just waited it out for a couple hours. The problem seemed to resolve on its own, so I'm guessing it was Coinbase.
Worst case scenario if this problem doesn't solve itself, is that you have to reset everything which requires you to send pics and whatnot to Coinbase to prove that you're actually the owner of that account, and this unfortunately is quite time consuming with how slow Coinbase is.
That's what I was trying to avoid. I'm guessing it takes days or even weeks to get an account unlocked this way.
So for future reference: if your clock is correct, give it a little time before contacting support. Sometimes their server time is temporarily off.