Problem setting up 2FA for the first time My devices:


iPad (iOS 10.3.1 (14E304)
MacBook Air (macOS 10.12.4 (16E195))
A ten-year-old BlackBerry that very definitely doesn't run iOS.


What works:


Apple have sent exactly one 2FA code to my phone, so I know absolutely they have got the correct phone number on their system and there is no typo there.
https://appleid.apple.com works fine, going through the login process results in a pop-up on my iPad and on my Mac showing my 6-digit verification code.
The website, the iPad, and the MacBook Air all show that both my iPad and my Mac are in my list of devices


What doesn't work:

iPad shows message (in Settings.app):


  Update Apple ID Settings
  Some account services require you to sign in again.


Pressing "Continue", entering my Apple ID password, then my device unlock code, leads to pop-over window saying:


  Approve This iPad
  
  Go to one of your other devices signed in to iCloud to approve this iPad.
  
  
  
  Waiting for approval…


And then it just sits there. Nothing else happens, no popup on any device.

Mac shows message (in Preferences.app > iCloud):


  Update Apple ID Settings
  Some account services require you to sign in again.


Pressing "Continue" (twice, because the first time shows the same message as a modal dialog), shows me a dialog for entering my Apple ID password (icon is a keyring, if that's relevant).

Entering my Apple ID password shows me "iCloud Preferences wants to make changes to your account. Type your password to allow this." (this only accepts my device account password, not that it's clear from the appearance).

Entering the password for my user account on my MacBook Air shows the following message on my MacBook Air:


  Go to one of your other devices signed in to iCloud to approve this MacBook Air.
  
     Waiting for approval…


And then it just sits there. Nothing else happens, no popup on any device.

Possibly relevant detail:


I have just changed my Apple ID email from a @yahoo.com domain to a @gmail.com domain.
Confirmation emails have come through just fine.
iCloud emails can be downloaded in Mail.app on the Mac (never set that email account up on the iPad)
(Edit) I have AdBlock Plus installed on both devices
I just had this same issue and tried many different things. In the end I resorted to contacting Apple who were extremely helpful. The thing to do is access another device which is logged in with the same iCloud account, and ensure that keychain is switched on. If it isn't, turn it on. From there just follow it through and if you have to reset your keychain data then do it. You'll then be able to get around the original 'Waiting for approval' issue on the initial device.