Update from last night and this morning. We cycled the power on the router and reinstalled the game before trying it out again this morning. First attempt at connecting got the error "The service could not find or create the lobby" - Second attempt got the error "Error: Could not connect to Lobby" - Third attempt he got into a lobby and was at the last moment before starting the match when he received the message "Error - you have been disconnected from the server."
The PS4 is wireless, ISP is Shaw. We had recently upgraded our router to improve performance, but when we ran the speedtest last night and this morning, the performance was on average: Download at 10.03Mbps; Upload at 6.46Mbps.
On a lighter note, the graphics look amazing and my son still can't wait to be up and running!!