My Nexus 5 prompted me to update my Android to 5.1. When I clicked download, the process is stuck on "Waiting to download..." and there after nothing happened. I waited for almost 10 minutes, and then restarted my phone yet again it stuck on same phase "Waiting to download..."
Edit: It took more than 15 minutes to initiate the download. So please wait patiently :D
(I am leaving the question open so that other users can share their answer on what they did to overcome this issue.)