Bootloader locked or unlocked makes no difference to the automatic update process, but it will have to be unlocked for any other method.
During the upgrade, if the update finds any system files that have been altered, it will throw an error, stop the install, and undo any changes made up to that point, including changes made by rooting. You could try un-rooting and waiting for the update to appear again, but the update will very likely fail again. No, I've not read of any sure-fire way to get the update to appear again more quickly.
It might be worth it to try to download the OTA update file from the internet and try to "adb sideload" it from within whatever Recovery you have. You can find the OTA update files a lot of places, but do make sure the update file matches both your CURRENT version as well as the TARGET version.
If that fails, there are a few methods of installing the whole factory image without losing data, but the easiest and most intuitive is the Nexus Root Toolkit (NRT) by WugFresh, especially for users that might not be comfortable with the command line.
Keep in mind that version 5.1.1 is already rolling out.