Can't check for watchOS update: "Update iPhone First"

I just enrolled to the Apple Beta Software program, and enrolled my Apple Watch.

Once I installed the watchOS 9 Beta Program profile and restarted the watch, I went to check for updates on my iPhone (SE 2nd generation, 2020) and it tells me to "Update iPhone First: To update your Apple Watch, you first need to update your iPhone. You can update your iPhone software in Settings. [Open Settings][Cancel]"

The thing is, my iPhone is up to date (iOS 16.3.1), at least that's what it tells me.

I already tried restarting my iPhone, disconnecting my watch from my iPhone and checking for updates in the watch itself, but it keeps telling me "Unable to Check for Update: An error occured while checking for a software update. [Cancel] [Try Again]"