I got the Deck today and I was having difficulty getting internet connectivity to work, and you need internet to be able to update and get in the main menu at all. I could connect to my router, but no internet connection. I was able to get the update using my phone as a hotspot, but after the update even that stopped working.

Afterwards, I went into desktop mode, and all you have to do is go in the system settings, under connections, go to your saved connection. On the right side go to the IPv6 tab, and change method to "Disabled". Disconnect and reconnect to the network, and that did it for me. I also let Steam know directly through their support, hopefully nobody else will be stuck like me.