I had the same problem, I finally got it working after a lot of trial and error. Not sure of the order of operations but this is what I did:
Move storage location in plex
stop server
go into android settings go to app details for plex media server
clear cache
go back to plex and start server, move storage location again if needed
reboot server and confirm storage location is still set correctly.
Eventually it worked, pretty sure the key step was clearing the plex media server cache in android app settings. Now rebooting doesn’t lose the storage location setting.
You may also want to sign up for the shield beta release as it may have also helped:
https://forums.geforce.com/default/topic/1090943/shield-tv/shield-experience-7-2-2-test-images/
