When the setup fails to complete here are a some things that some people have found to work for them. They may not be universally successful, but they are at least worth a try.
A) Easiest to try, so try this first: Restart your router, even if other devices on the network are not having problems. When your router has completed its startup, try repeating your Roku setup.
B) If you are powering your Roku by plugging into the USB port on the TV, try powering from house power via a USB power adapter, as some TV USB ports don't supply enough power to drive a Roku reliably. If your Roku didn't come with an adapter, or if you don't have a Roku adapter handy, another USB power adapter you have from another device should work as long as the fine print on it says it outputs at least 1 amp.
C) Try using a different WiFi network to do the update - perhaps via a WiFi hotspot on your mobile phone or by taking it to a friend's house - and see if it will complete the startup. If successful, then redo the WiFi connection to use your intended WiFi network via Settings > Network > Set up connection. Why this works, when it does, I haven't a clue.
