I've got a variant of this problem now since having to change the email address tagged to my Youtube account.
Try to link account -> go through the motions (have tried the google+ and youtube accounts so far) -> PS4 tells me everything worked.
However, nothing is actually getting authorized, nothing appears in the authorized apps list at Google under any account, and the PS4 acts like I've never done this before. Everything had been perfect until that account change
Out of interest I created a totally new bogus Youtube channel and exactly the same thing happened.
Edit: tried again today, everything behaved as yesterday except magically it works now..
Edit: broke again.
Ok - I've worked it out - it's to do with old pre-Google Youtube accounts, what I don't understand is why changing my email address triggered it. What you need to do is check your account - you'll find you'll have a
xxxxxx@pages.plusgoogle.com one, your Youtube one, and one for the google+ account it was "migrated" to.
Make sure those last two don't have a channel at all by becoming those accounts and checking under advanced. If they do and you don't use them, delete them. Then go back to your proper Youtube account, again go to advanced and make your Youtube channel the default for (youremailaddress used for google+).
Then do the PS4 side setup again.
What a mess.
Edit: no, worked for 3-4 uploads but it's broken again now. Given the amount of time my machine is spending spinning the 'busy' icon between these steps I'm starting to think it's something to do with my ISP or Sony.